# LLaVA-Gemma: Accelerating Multimodal Foundation Models with a Compact
Language Model

Musashi Hinck111Equal Contributions, order decided by LLaVA-Gemma 2b Matthew
L. Olson111Equal Contributions, order decided by LLaVA-Gemma 2b David Cobbley
Shao-Yen Tseng  Vasudev Lal
Cognitive AI, Intel Labs
Santa Clara, CA USA
{musashi.hinck,matthew.lyle.olson,david.j.cobbley,shao-
<EMAIL_ADDRESS>
###### Abstract

We train a suite of multimodal foundation models (MMFM) using the popular
LLaVA framework with the recently released Gemma family of large language
models (LLMs). Of particular interest is the 2B parameter Gemma model, which
provides opportunities to construct capable small-scale MMFMs. In line with
findings from other papers in this space, we test the effect of ablating three
design features: pretraining the connector, utilizing a more powerful image
backbone, and increasing the size of the language backbone. The resulting
models, which we call LLaVA-Gemma, exhibit moderate performance on an array of
evaluations, but fail to improve past the current comparably-sized SOTA
models. Closer analysis of performance shows mixed effects; skipping
pretraining tends to reduce performance, larger vision models sometimes
improve performance, and increasing language model size has inconsistent
effects. We publicly release training recipes, code and weights for our models
for the LLaVA-Gemma models111https://huggingface.co/intel/llava-gemma-2b/,
https://huggingface.co/intel/llava-gemma-7b/ .

##  1 Introduction

In this paper, we introduce LLaVA-Gemma, a suite of vision-language assistants
trained from the Gemma Large Language Model (LLM) variants, Gemma-2B and
Gemma-7B [17]. Our work is inspired by the rapid progress in small but capable
visual language models (VLMs), such as LLaVA-Phi [23], which have demonstrated
remarkable efficiency and effectiveness in various language understanding
tasks. LLaVA-Gemma distinguishes itself among small VLMs due to the public
release of similarly trained, different-sized LLMs Gemma-2B and Gemma-7B.

The unique release of the Gemma models offers an opportunity to contrast model
performance in relation to parameter size and visual encoding capabilities. By
possessing two variants with different parameter sizes, LLaVA-Gemma allows
researchers to investigate the trade-offs between computational efficiency and
the richness of visual and linguistic understanding. With these two variants,
we perform a deeper exploration of how varying levels of model complexity
influence the effectiveness of visual encoding, providing valuable insights
into the optimization of small VLMs for diverse tasks and environments.
Furthermore, the use of significantly more unique tokens, at $256k$, offers an
opportunity to investigate how a massively increased token set effects multi-
modal performance.

Recent advancements in (LLMs) [20] and multimodal foundation models (MMFMs)
[7] have propelled the interest and development of Large Multimodal Models
(LMMs). Notable models like GPT-4 [1], LLaVA [10, 9], and their derivatives
have demonstrated significant performance in vision-language tasks such as
Visual Question Answering (VQA) and image captioning [5]. However, the
computational demands of deploying these models have led to the exploration of
small-scale LMMs. Our work aims to provide a unified analysis of small-scale
LMMs, examining how model selections, training recipes, and data contribute to
performance, which is distinct from existing works such as LLaVA-Phi.

Our contributions are as follows:

  1. 1.

We introduce LLaVA-Gemma, a MMFM that leverages the compact yet powerful Gemma
language models for efficient multimodal interactions.

  2. 2.

We extensively evaluate Gemma-2B and Gemma-7B model variants provides valuable
insights into the trade-offs between computational efficiency and the richness
of visual and linguistic understanding in LLMs.

  3. 3.

We present a deep exploration into alternate design choices and visualize
attention with relevancy maps to enhance our understanding of the model’s
performance and attention.

Language | Vision | Pretrain |  | MME | MM- | POPE |  |  | ScienceQA
---|---|---|---|---|---|---|---|---|---
Backbone | Backbone | Connector | GQA | Cog. | Per. | Vet | Acc. | F1 | VQAv2 | MMVP | Image
gemma-2b-it | CLIP | Yes | 0.531 | 236 | 1130 | 17.7 | 0.850 | 0.839 | 70.7 | 0.287 | 0.564
gemma-2b-it | CLIP | No | 0.481 | 249 | 935 | 13.1 | 0.784 | 0.762 | 61.7 | 0.180 | 0.549
gemma-2b-it | DinoV2 | Yes | 0.587 | 307 | 1133 | 19.1 | 0.853 | 0.838 | 71.4 | 0.227 | 0.555
gemma-2b-it | DinoV2 | No | 0.501 | 309 | 959 | 14.5 | 0.793 | 0.772 | 61.7 | 0.180 | 0.568
gemma-7b-it | CLIP | Yes | 0.472 | 254 | 895 | 18.2 | 0.848 | 0.829 | 68.7 | 0.327 | 0.625
gemma-7b-it | CLIP | No | 0.472 | 278 | 857 | 19.1 | 0.782 | 0.734 | 65.1 | 0.240 | 0.636
gemma-7b-it | DinoV2 | Yes | 0.519 | 257 | 1021 | 14.3 | 0.794 | 0.762 | 65.2 | 0.327 | 0.628
gemma-7b-it | DinoV2 | No | 0.459 | 226 | 771 | 12.2 | 0.693 | 0.567 | 57.4 | 0.267 | 0.598
Phi-2b | CLIP | Yes | - | - | 1335 | 28.9 | - | 0.850 | 71.4 | - | 0.684
Llama-2-7b | CLIP | Yes | 0.620 | 348 | 1511 | 30.6 | 0.850 | 0.859 | 78.5 | 46.1 | 0.704
Table 1: Performance of LLaVA-Gemma models across seven benchmarks.
Highlighted box indicates strongest performance amongst LLaVA-Gemma models.
Bottom two rows show self-reported performance of Llava Phi-2 and LLaVA-v1.5
respectively.

##  2 Methods

We follow the LLaVA framework [9] with a few design modifications. This
framework combines a pretrained vision encoder (such as CLIP [14]) and
pretrained language model (such as Llama-2 [19]) into a multimodal model using
a MLP connector and a two-stage training procedure.

The first stage pretrains the MLP connector by freezing the vision and
language models and training on custom dataset of 595k samples filtered from
CC3M [15]. The second stage jointly finetunes the language model and connector
using a custom mixture 665k multimodal instruction tuning examples. This
dataset includes synthetic data generated [10], as well as examples from
established vision-language training sets such as GQA [5] and TextCaps [16].

We deviate from the original recipe in three ways: the language model, the
vision encoder and the pretraining stage. For the language backbone, we use
the recently released Gemma models [17]. Two aspects of Gemma make it an
interesting candidate for our experiments. Whereas LLaVA uses the 7 and
13-billion parameter vicuña langauge models [22], Gemma offers 2 and 7-billion
parameter versions. Next, Gemma uses a significantly larger token set than any
other LLM, with 256k unique tokens (compared to a standard 50k), which offers
a unique opportunity to see the effects of a massively more diverse embeddings
space. Other papers exploring the design space of Vision Language Models
(VLMs) find the vision encoder is important for achieving strong performance
[12]. Correspondingly, we explore the use of the larger 1-billion parameter
DINOv2 image encoder [13] as the vision tower. Related work on VLMs [6] finds
that skipping the initial pretraining stage improves downstream performance.
For all designs, we train a version with and without the initial pretraining
step.

##  3 Results

We evaluate the LlaVA-Gemma models on a similar collection of benchmarks to
other LMM works: GQA [5]; MME [3]; MM-Vet [21]; POPE (accuracy and F1) [8];
VQAv2 [4]; MMVP [18]; the image subset of ScienceQA [11]. Our experiments
provide insights into the efficacy of various design choices within the LLaVA
framework. As shown in table 1, the performance of LLaVA-Gemma models across
seven benchmarks reveals interesting patterns, particularly concerning the
choice of vision encoder and the impact of pretraining the connector.

###  3.1 Influence of Vision Encoder on Performance

For the 2B backbone, exchanging the CLIP vision encoder for DinoV2 appears to
generally improve performance, with DinoV2 variants outperforming CLIP
variants on all benchmarks except POPE-F1 and MMVP. When using a 7B backbone,
the picture is murkier; although we see improvements for GQA and MME, we see a
decline in performance on MM-Vet, POPE, VQA and ScienceQA. This may suggest an
interaction between the capability of the language model and the richness of
the representation provided by the vision encoder, or to the possibility that
the 7b-Dino combination is undertrained.

###  3.2 Effects of Pretraining

We find that skipping the initial connector pretraining almost always reduces
model performance. With the exceptions of 2B-Dino on MME Cognition and 7B-CLIP
on MME Cognition, MM-Vet and ScienceQA, the variant with a pretrained
connector outperforms its counterpart that skipped pretraining. These results
do not support the hypothesis posited in Karamcheti et al. [6].

###  3.3 Comparison to Baselines

Contrasting the results of LLaVA-Gemma with the self-reported performances of
Phi-2b and Llama-2-7b models provides additional context. The LLaVA-Gemma
models only reach parity on comparably-sized baselines for the VQA benchmark
between 2B models. Given the absence of strong a priori reasons to expect
Gemma-based LLaVA models to perform worse, understanding this “poor”
performance is a direction of future interest.

###  3.4 Speed of Training and Inference

We compare the training and eval speed for the two models sizes. In our
experiments, the training time for the Gemma-2B model on 8 Intel Gaudi 2® AI
accelerators was 4 hours, while the larger Gemma-7B model required 16 hours to
train under the same conditions. This indicates that the Gemma-7B model, with
its increased parameter count, takes approximately four times longer to train
compared to the Gemma-2B model. The relative speed of the Gemma-7B model is
thus 0.25x compared to the Gemma-2B model. These results highlight the trade-
off between model size and training efficiency, with larger models requiring
significantly more computational resources and time.

##  4 Analysis

###  4.1 Impact of Alternate Design Choices

Figure 1: Effect of design choices differs between evaluations. Point
indicates average change in probability of correct answer versus baseline
design.

Table 1 suggests that the gemma-2b-dino recipe generally provides stronger
evaluation results, but these results are mixed. To better assess the effect
of the design choices, we fit a collection of linear models to measure the
average associated change in the probability of a correct prediction as a
function of each of the three ablations: skipping pretraining, changing the
vision backbone, and increasing the size of the LM backbone from 2B to 7B. We
study these effects separately for each benchmark.

Figure 1 shows the average effects of design choices for four benchmarks where
we have observation-level errors. Skipping pretraining appears to either have
a strong negative (GQA, POPE) or weak/insignificant effect (MME, ScienceQA).
Changing the vision encoder to DinoV2 improves performance on GQA and MME, but
slightly worsens performance on POPE and has no significant effect on the
probability of correct predictions on ScienceQA. Notably, in our experiments
increasing the LM backbone to the 7B parameter variant had a strong negative
effect on GQA, MME and POPE, but strong positive effect on ScienceQA. Taken
together, these heterogeneous results underscore the need for more granular
analysis of errors and design choices.

###  4.2 Visualizing Attention with Relevancy Maps

To better understand the differences between our the LLaVA-Gemma models, we
use relevancy maps [2] to visualize where the model focuses its attention.
These relevancy maps provide a token-wise understanding of the model’s
attention by highlighting the most relevant parts of the input and is
specially designed to maintain the total relevancy across layers for
transformer based models.

We apply an qualitative example of these relevancy maps from the Eyes-wide-
shut (MMVP) dataset. This dataset is of particular interest as it is designed
to find image-caption pairs that a CLIP model finds to be similar, but are
distinct. As the traditional LLaVA recipe uses CLIP, we compare our CLIP
backboned models to find a case where the Gemma 2b model fails, but Gemma 7b
is successful.

Figure 2: Relevancy map comparison between LLaVA-Gemma 2b (Left) and LLaVA-
Gemma 7b (Right) with gradients on the first relevant output token. For the
question “Is the duck floating? (a) Yes (b) No”, despite using the identical
CLIP vision encoder, the smaller model does not attend to the visual input.

Figure 2 shows an example of the differences in attention to the visual
aspects of the scene between the LLaVA-Gemma 2b and LLaVA-Gemma 7b models. The
relevancy maps for the LLaVA-Gemma 2b model show a dispersed and unfocused
pattern of attention, which correlates with its failure to accurately
interpret the scene. In contrast, the LLaVA-Gemma 7b model exhibits a more
concentrated and relevant pattern of attention, particularly focusing border
between objects: the duck, the water, and the rock being stood on. This
visualization not only highlights the superior performance of the LLaVA-Gemma
7b model, but also illuminates an interesting case where leveraging a more
powerful LLM ensures improved visual token attention.

##  5 Discussion

In this paper, we introduced LLaVA-Gemma, a compact vision-language model
leveraging the Gemma Large Language Model in two variants, Gemma-2B and
Gemma-7B. Our work provides a unique opportunity for researchers to explore
the trade-offs between computational efficiency and multimodal understanding
in small-scale models. The availability of both variants allows for a
comparative analysis that sheds light on how model size impacts performance in
various tasks. Our evaluations demonstrate the versatility and effectiveness
of LLaVA-Gemma across a range of datasets, highlighting its potential as a
benchmark for future research in small-scale vision-language models. With
these models, future practitioners can optimize the performance of small-scale
multimodal models more directly.

## References

  * Achiam et al. [2023] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, et al.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Chefer et al. [2021] Hila Chefer, Shir Gur, and Lior Wolf.  Generic attention-model explainability for interpreting bi-modal and encoder-decoder transformers.  In _Int. Conf. Comput. Vis._ , pages 397–406, 2021.
  * Fu et al. [2023] Chaoyou Fu, Peixian Chen, Yunhang Shen, Yulei Qin, Mengdan Zhang, Xu Lin, Jinrui Yang, Xiawu Zheng, Ke Li, Xing Sun, Yunsheng Wu, and Rongrong Ji.  Mme: A comprehensive evaluation benchmark for multimodal large language models.  _arXiv preprint arXiv:2306.13394_ , 2023.
  * Goyal et al. [2017] Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh.  Making the v in vqa matter: Elevating the role of image understanding in visual question answering.  In _IEEE Conf. Comput. Vis. Pattern Recog._ , pages 6904–6913, 2017.
  * Hudson and Manning [2019] Drew A Hudson and Christopher D Manning.  Gqa: A new dataset for real-world visual reasoning and compositional question answering.  In _IEEE Conf. Comput. Vis. Pattern Recog._ , pages 6700–6709, 2019.
  * Karamcheti et al. [2024] Siddharth Karamcheti, Suraj Nair, Ashwin Balakrishna, Percy Liang, Thomas Kollar, and Dorsa Sadigh.  Prismatic vlms: Investigating the design space of visually-conditioned language models.  _arXiv preprint arXiv:2402.07865_ , 2024.
  * Li et al. [2023a] Chunyuan Li, Zhe Gan, Zhengyuan Yang, Jianwei Yang, Linjie Li, Lijuan Wang, and Jianfeng Gao.  Multimodal foundation models: From specialists to general-purpose assistants.  _arXiv preprint arXiv:2309.10020_ , 1(2):2, 2023a.
  * Li et al. [2023b] Yifan Li, Yifan Du, Kun Zhou, Jinpeng Wang, Wayne Xin Zhao, and Ji-Rong Wen.  Evaluating object hallucination in large vision-language models.  _arXiv preprint arXiv:2305.10355_ , 2023b.
  * Liu et al. [2023] Haotian Liu, Chunyuan Li, Yuheng Li, and Yong Jae Lee.  Improved baselines with visual instruction tuning.  _arXiv preprint arXiv:2310.03744_ , 2023.
  * Liu et al. [2024] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee.  Visual instruction tuning.  _Adv. Neural Inform. Process. Syst._ , 36, 2024.
  * Lu et al. [2022] Pan Lu, Swaroop Mishra, Tanglin Xia, Liang Qiu, Kai-Wei Chang, Song-Chun Zhu, Oyvind Tafjord, Peter Clark, and Ashwin Kalyan.  Learn to explain: Multimodal reasoning via thought chains for science question answering.  _Adv. Neural Inform. Process. Syst._ , 35:2507–2521, 2022.
  * McKinzie et al. [2024] Brandon McKinzie, Zhe Gan, Jean-Philippe Fauconnier, Sam Dodge, Bowen Zhang, Philipp Dufter, Dhruti Shah, Xianzhi Du, Futang Peng, Floris Weers, et al.  Mm1: Methods, analysis & insights from multimodal llm pre-training.  _arXiv preprint arXiv:2403.09611_ , 2024.
  * Oquab et al. [2023] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al.  Dinov2: Learning robust visual features without supervision.  _arXiv preprint arXiv:2304.07193_ , 2023.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Sharma et al. [2018] Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In _ACL_ , pages 2556–2565, Melbourne, Australia, 2018. Association for Computational Linguistics.
  * Sidorov et al. [2020] Oleksii Sidorov, Ronghang Hu, Marcus Rohrbach, and Amanpreet Singh.  Textcaps: a dataset for image captioning with reading comprehension.  In _Eur. Conf. Comput. Vis._ , pages 742–758. Springer, 2020.
  * Team et al. [2024] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al.  Gemma: Open models based on gemini research and technology.  _arXiv preprint arXiv:2403.08295_ , 2024.
  * Tong et al. [2024] Shengbang Tong, Zhuang Liu, Yuexiang Zhai, Yi Ma, Yann LeCun, and Saining Xie.  Eyes wide shut? exploring the visual shortcomings of multimodal llms, 2024.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, et al.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Adv. Neural Inform. Process. Syst._ , 30, 2017.
  * Yu et al. [2023] Weihao Yu, Zhengyuan Yang, Linjie Li, Jianfeng Wang, Kevin Lin, Zicheng Liu, Xinchao Wang, and Lijuan Wang.  Mm-vet: Evaluating large multimodal models for integrated capabilities.  _arXiv preprint arXiv:2308.02490_ , 2023.
  * Zheng et al. [2023] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, et al.  Judging llm-as-a-judge with mt-bench and chatbot arena, 2023.
  * Zhu et al. [2024] Yichen Zhu, Minjie Zhu, Ning Liu, Zhicai Ou, Xiaofeng Mou, and Jian Tang.  Llava-phi: Efficient multi-modal assistant with small language model.  _arXiv preprint arXiv:2401.02330_ , 2024.


Hashing it Out: Predicting Unhealthy Conversations on Twitter

Steven Leung1, Filippos Papapolyzos2

1 UC Berkeley
2 UC Berkeley

<EMAIL_ADDRESS>
## Abstract

Personal attacks in the context of social media conversations often lead to
fast-paced derailment, leading to even more harmful exchanges being made.
State-of-the-art systems for the detection of such conversational derailment
often make use of Deep Learning approaches for prediction purposes. In this
paper, we show that an Attention-based BERT architecture, pre-trained on a
large Twitter corpus and fine-tuned on our task, is efficient and effective in
making such predictions. This model shows clear advantages in performance to
the existing LSTM model we use as a baseline. Additionally, we show that this
impressive performance can be attained through fine-tuning on a relatively
small, novel dataset, particularly after mitigating overfitting issues through
synthetic oversampling techniques. By introducing the first transformer based
model for forecasting conversational events on Twitter, this work lays the
foundation for a practical tool to encourage better interactions on one of the
world’s most ubiquitous social media platforms.

##  1 Introduction

Social media has become one of the primary stages where peer-to-peer
discussions take place, spanning anything from everyday local matters to high
level philosophical topics. A very frequent phenomenon that is noticed in such
conversations is their rapid deterioration upon the presence of a personal
attack, often leading to personal threats and insults which heavily undermine
the level of discussion. In order to battle this issue, Social Media
companies, such as Twitter and Facebook, have come up with systems that make
use of human moderators who review content flagged by users. In the majority
of cases, content that goes against the company’s policy is removed [13].

The way this moderation tactic is set up presents a series of challenges and
limitations, the most obvious being the cost of moderation services. Secondly,
there have been cases of unreliable moderation in Twitter, with users
receiving temporary bans simply for mentioning some specific word in their
tweets. Lastly, it has to be appreciated that moderation can be quite an
emotionally taxing job as content under review will often be very disturbing.

The most basic limitation of this approach, however, is that moderation only
happens a posteriori and solely after users choose to report the abusive
content. This leaves a significant space in time in which a conversation can
escalate further and users might become the victims or perpetrators of
personal attack and/or verbal abuse. To the best of our knowledge, no effort
is done on the part of Twitter in order to prevent such harmful content rather
than moderate it. We trust that if Social Media companies chose to assume a
preventative strategy to moderation, this would reduce the instances of
personal attacks and improve the overall content quality.

There are a series of issues that make detecting potentially harmful language
a challenging topic. As mentioned in Twitter’s enforcement policy [13],
context is of utmost importance; the use of specific language might have a
different interpretation when the preceding conversation is better examined.
Twitter’s policy mentions that factors such as whether “the behavior is
directed at an individual, group, or protected category of people” and “the
severity of the violation” are also considered prior to taking action.

The aim of this project is to provide a Deep Learning approach to content
moderation, by means of an attention-based neural network model that predicts
whether a Twitter conversation is likely to deteriorate and lead to a personal
attack. We believe that this will not only provide an advantage to moderators
but could also potentially be utilized to give warnings to users when they are
about to tweet something which may lead to escalation.

##  2 Related Work

A lot of our inspiration for this project was drawn from the 2018 paper
Conversations Gone Awry: Detecting Early Signs of Conversational Failure
(Zhang et al., 2018) [17]. Specifically, in this paper the authors try to
identify predictors of conversational derailment and make predictions using a
variety of strategies. An interesting insight from the paper is that
conversations containing an attacker-initiated direct question are most likely
to derail. The authors also claim that human-based predictions of
conversational derailment are at an accuracy level of 72%.

Past work has also been done on forecasting hostility on a dataset of
Instagram comments (Liu et al., 2018) [7], analyzing features of personal
attack in Wikipedia comments (Wulczyn et al., 2017) [16] and the use of
attention models to improve the performance of RNN and CNN approaches to
content moderation (Pavlopoulos et al., 2017) [9].

In the 2019 paper titled Trouble on the Horizon: Forecasting the Derailment of
Online Conversations as they Develop, Chang et al. [2], the authors use a
Recurrent Neural Network (RNN) based approach to predict conversational
derailment on a dataset of Wikipedia talk page discussions developed as part
of the aforementioned 2018 paper, and a dataset of conversations in the
ChangeMyView subreddit. CRAFT, their model architecture, yields an accuracy
score of 66.5% which, to the best of our knowledge, is the highest accuracy
score achieved on this specific task.

Despite the success of the RNN-based CRAFT model, we choose to explore a pre-
trained self-attention model for our conversational task for several reasons.
First, work by Vaswani et al. [14], and others have shown performance
advantages of transformers vs RNNs. Namely, RNNs have displayed challenges
with long range dependencies and word sense disambiguation relative to
transformers [12]. We deemed that using an Attention model could allow us to
curb the sequential architecture of RNNs, allowing the model to make use of
previous context without information loss. This is grounded in the idea that
previous tweets in a conversation may have an equally strong effect on the
probability of derailment of a subsequent tweet. In addition, transfer
learning allows us to take advantage of pre-trained models, such as BERTweet,
which is trained on millions of examples in the unique language of Twitter,
thus improving the overall performance of our approach. Finally, due to the
linear scaling self-attention models as opposed to the quadratic scaling of
RNNs, our model is more scalable to the vast conversational world of Twitter.

##  3 Dataset

For this project we have compiled our own dataset, consisting of 5656 tweets
tagged on one binary dimension of personal attack. Tweets are labelled with
conversation ID’s, vital for our task of using prior tweets to predict the
outcome of a subsequent tweet. We acquired our data through the Twitter API.
In order to have a higher probability of finding positive examples of personal
attack, we selected conversations from a collection of controversial topics
such as Universal Basic Income, abortion, and immigration.

In tagging each tweet as either containing a personal attack or not, we used
the Wiktionary definition of a personal attack: ”an abusive remark on or
relating to somebody’s person instead of providing evidence when examining
another person’s claims or comments”. We used three methods in tagging. First,
we made use of the participant recruitment platform Mechanical Turk. Secondly,
we were fortunate enough to find a dataset on Zenodo titled “Hate speech and
personal attack dataset in English social media” [3] that contained tweet
level tags. We were able to match these tweets to the rest of the conversation
through the Twitter API. Finally, we tagged the remainder of tweets ourselves.

From the 5656 tweets, we isolated 1177 positive examples, leaving 4479
negative examples which translated to a heavy class imbalance. Our budget and
project time frame were significant limitations to the quality and scale of
our data collection, forcing us to seek alternative methods of reducing the
effect of positive example under-representation, which came at their own
costs. Specifically, we made use of oversampling for positive examples, which
came at the expense of overfitting.

###  3.1 Synthetic Oversampling

A method we made use of to reduce class imbalance in our dataset was a
technique called synthetic oversampling. Specifically, we deemed that by
creating artificial context examples for the positive class and supplying them
to our model in the training phase we could reduce the effect of overfitting
while also providing a larger quantity of plausible training examples. This
technique works by replacing words in the original context with similar words
to create new contexts and resupplying them to the model as separate training
examples.

Our inspiration was drawn from the 2016 paper A Study of Synthetic
Oversampling for Twitter Imbalanced Sentiment Analysis (Ah-Pine & Soriano,
2016) [1] in which the authors present a general algorithm for creating
synthetic samples as follows: a random tweet x is drawn from a distribution P,
its nearest neighbors NN(x) are determined, a neighbor x’ is chosen “according
to a probability distribution over NN(x)” and a synthetic sample is created in
the form $y=x+a(x’-x)$, where $a~{}unif(0,1)$. A popular version of this
algorithm is known as SMOTE (Synthetic Minority Oversampling TEchnique)
(Chawla, 2002) [4], which assumes a uniform distribution over P. The
application of this algorithm in the context of words requires a vector space
mapping which, in our case, was achieved using the GloVe Twitter Embeddings.

Specifically, the original context is first broken down into a series of
tokens which are tagged by part-of-speech and are filtered for stopwords,
which are not further processed. Using the GloVe Twitter embeddings, a
dictionary of k-nearest neighbors is computed for each token using the
Euclidean distance metric. We randomly pick one of the 3 closest neighbors
with non-uniform probability, giving larger probability to the closest
neighbor. We then randomly choose the filtered tokens to be replaced in the
original context with probability P = 0.2 and repeat this process n times to
produce a list of similar but non-identical contexts. Using this process we
developed 355 synthetic positive examples.

##  4 Transformer Model

Our general model for forecasting conversational events is the BERT-base
BERTweet transformer model, fine-tuned on our conversational Twitter data.

###  4.1 Conversational Structure

##### Conversations

For the purposes of our model, a conversation is made up of an initial tweet
(what we call a top-level tweet) and all subsequent tweets following that
tweet that are in direct reply to one another. While Twitter does allow for
the branching of conversations (at any point in a conversation, users can
reply directly to the top-level tweet or to a reply, a reply of a reply, etc.)
that allows for complex conversational structures, we limit our model to
looking at single conversational branches at a time for each input.

Thus, given top-level tweet T1, a conversation consists of a sequence of N
tweets $C=\\{T_{1},...,T_{N}\\}$

##### Context

Tweets are the individual components of the conversation, made by a single
user. For the sake of forecasting, we are using the two tweets prior to
forecast whether the current tweet in question will be a personal attack. The
two tweets prior are referred to as the ”context”. This is the input into our
model.

The two context tweets are concatenated with the $</s>$ token in between to
preserve the delineation of tweets. The context is then tokenized using the
BERTweet tokenizer, with a normalization feature to handle common
conversational elements in Twitter such as username handles, hashtags and
urls. The classification token, $[CLS]$, is appended to the front of the input
for use in the classification process. Thus, given the tweet in question,
$T_{N}$, the two tweet context, $T_{N}-1$ and $T_{N}-2$, is converted to
variable M length tokens, yielding the conversational context,
$C_{N}=[CLS],T_{N-1,1},T_{N-1,2},T_{N-1,...},T_{N-1,M}</s>,T_{N-2,1},T_{N-2,2},T_{N-2,...},T_{N-2,M}$

The most recent tweet in the context is placed in the front of the context to
avoid truncating the most recent tweet in the case that the context exceeds
BERTweet tokenizer’s 130 token length limit.

Figure 1: Model architecture. The tokenized two tweet context is fed into pre-
trained BERTweet. Forecasting whether the subsequent tweet will be a personal
attack or not is treated as a classification problem through a logistic
regression head on the CLS token final embedding.

###  4.2 Fine-tuning BERTweet

The pre-trained BERTweet model that we use is a fine-tuned version of the
popular BERT model. At a high-level, BERT is a bi-directional encoder model
trained to predict masked tokens and whether one sentence directly follows
another in the source text [5]. We use the base model configuration consisting
of 12 transformer blocks, 12 self-attention heads, and a hidden size of 768.
In the BERTweet implementation, BERT base is fine-tuned on 850M tweets for
optimal performance on Twitter data in regards to the tasks of part-of-speech
tagging, named-entity recognition and text classification [8]. We choose this
pre-trained model based on its superior performance to other transformer
models such RobertaLarge and XLM-R large, specifically on Twitter data on the
tasks mentioned above.

During the fine-tuning process, we update the parameters of BERTweet on the
specific task of personal attack forecasting using Twitter conversation
context in accordance with the method proposed in Howard et al. [6]. We append
a classification head on top of BERT using the huggingfaces model configuation
Bertforsequenceclassification [15]. In this implementation, the $[CLS]$ token
is used to classify whether the tweet in question is forecasted to be a
personal attack or not, in that the final hidden state $h$ of this token is
used to classify the sequence. A simple linear dense layer classification head
is added to the top of BERTweet to forecast the probability of a personal
attack before passing to a sigmoid transformation for binary classification:

$\begin{split}{P}(\text{Attack}\mid\text{$h_{1...768}$})=\text{Sigmoid}(W\text{$h_{1...768}$}+b)\end{split}$
(1)

This classification method is discussed in further depth by Sun et al. [11].

##  5 Evaluation and Analysis

###  5.1 Results

We test and evaluate three models to examine the effect of both the model
architecture and synthetic oversampling. We use the CRAFT model as our
baseline in the same form as proposed by Chang et al.. CRAFT is trained and
evaluated on our Twitter conversation data using standard oversampling on the
positive class. We then fine-tune and evaluate BERTweet with standard
oversampling to measure the impact of a transformer implementation as opposed
to the LSTM implementation proposed in CRAFT. Finally, we fine-tune and
evaluate BERTweet on our Twitter conversation data with synthetic oversampling
of the positive class.

Model | A | P | R | F1 | AUPR
---|---|---|---|---|---
CRAFT | 0.76 | 0.52 | 0.57 | 0.54 | 0.55
BT | 0.82 | 0.62 | 0.76 | 0.68 | 0.76
BT SOS | 0.85 | 0.69 | 0.72 | 0.70 | 0.78
Table 1: Comparison of performance between CRAFT with random oversampling
(CRAFT), BERTweet fine-tuned with random oversampling (BT) and BERTweet fine-
tuned with synthetic oversampling (BT SOS). Classification threshold of .5.

We evaluate our model in relation to several key metrics - including total
accuracy on both positive and negative classes and precision, recall, F1 score
and area under the precision recall curve for the positive class. While it is
of vital importance to flag as many upcoming personal attacks as possible
(recall), it is also of crucial importance to maintain credibility by not
flagging innocuous conversations (precision). Thus, we pay particular
attention to the area under the precision recall curve (AUPR) as a measure of
success. This method is preferable to the ROC curve due to the high class
imbalance. The AUPR metric was used heavily in the ”Trouble on the Horizon”
paper, in which the authors achieved an AUPR of .70 on their final model [2],
although we do not make an explicit comparison to this result due to the
disparate nature of our conversational data.

Figure 2: Precision-recall curves and the area under each curve.

The transformer based BERTweet model outperforms the LSTM based CRAFT model in
all metrics. Implementing synthetic oversampling also improves all metrics,
with the exception of recall on the positive class on the classification
threshold of .5. Given the higher AUPR score, however, we see that synthetic
oversampling has generally improved our model’s ability to classify the
positive class.

###  5.2 Analysis

We now examine the behavior of our model to better understand what aspects of
the data it is using for predictions and where it is falling short.

####  5.2.1 Model Behavior

##### The Lead Up to an Attack

We first examine whether the model is using the full two tweet context we are
supplying to make its predictions or if a single tweet context is sufficient.
Intuitively, we expected only a minor drop in performance since our assumption
was that most of the signal indicating an attack was coming would be captured
in the tweet immediately preceding the attack tweet. We tested this hypothesis
by truncating the training data to a single tweet. We were surprised to see a
dramatic drop in performance, with the model performing at .74 accuracy and
only .50 AUPR. This indicates that the tweet two prior does indeed provide a
large amount of useful information in making predictions.

##### Conversational Dynamics

Secondly, we look at whether the model is using information about
conversational dynamics in the context to inform its predictions. To look at
this, we remove the tweet separator token, $</s>$, so that any indication of
delineation between speakers is lost. Model performance again drops, although
not as significantly as in our first test, with an accuracy of .77 and AUPR of
.76. This meets our expectation since the location of inflammatory language
that leads to a personal attack relative to the token (in other words, which
tweet in the context it is in) would presumably be valuable information for
the model to use in making a prediction on the current tweet.

####  5.2.2 Model Limitations

##### Limited Dataset

While building our model, one of the major challenges we faced was the
relatively small size of the dataset we were fine-tuning on, particularly in
the positive class. The main consequence of this was a tendency of our model
to overfit the training dataset. We dealt with this issue through a variety of
methods, including synthetic oversampling (as mentioned earlier), reducing
batch size to 10, maintaining the learning rate at the default level of 5e-5
and ensuring that training did not exceed 4 epochs.

Even so, we occasionally see unusual spikes in the negative log likelihood
loss pattern on the validation set related to our limited dataset. These
spikes would occur despite an increasing accuracy and AUPR score. In other
words, our model is making more correct predictions on the positive and
negative class on our validation data but is also more over-confident in the
bad predictions it is making. We posit two potential explanation for this.
Firstly, despite the measures above, our model is likely still overfitting to
an extent on the training data. This leads to over-confident incorrect
predictions due to random noise as opposed to true signal in our validation
data. Secondly, due to the small number of positive examples in our validation
set (154), a small change in parameters between epochs could result in
dramatic swings in total loss. In other words, a few very bad predictions
could have a large impact on the loss calculation, resulting in the spike we
witnessed.

##### GIF Confusion

We observe a higher occurrence of url strings in the context strings where our
model makes misclassifications on the test set. The ratio of url strings to
context strings is .65 in the misclassified examples vs only .5 in the
correctly classified examples. This makes sense intuitively since these url
strings contain a large amount of information relative to whether a personal
attack is coming that is not interpretable by our model. The best example of
this is GIFs, or animated images. While these GIFs are represented in our data
as simple url strings, the actual content of the GIF could be highly
inflammatory, benign or even friendly, which could be highly indicative of the
presence or absence of a personal attack in the subsequent tweet. While we did
not have time to explore this further, we believe this would be a fruitful
area of future work, as we will discuss in more detail in the future work
section.

##### Nuanced Langugage

In their paper, Price et al. note the difficulty for neural models to identify
nuanced language that indicates negative interactions such as sarcasm,
dismissiveness, and condescension. [10]. Notably, BERT was shown by the
authors to be particularly poor at identifying sarcasm. These are language
qualities that could be highly indicative of impending personal attacks. Since
this is not currently accounted for in our model, we believe this is likely a
source of confusion contributing to our existing loss.

##  6 Conclusions and Future Work

In summary, we introduced a transformer based model for forecasting
conversational events on a novel dataset of Twitter conversations. This model
indicates some ability to understand conversational dynamics between speakers.
It fills a void in the existing literature in that it provides state-of-the-
art predictive performance on Twitter, a platform that has not been studied in
the space of conversational forecasting.

Given Twitter’s stated goal of having healthier conversations on its platform,
we hope this study is a foundation for future work specific to this ubiquitous
channel of communications. One vital area of expansion will be to incorporate
additional topics of conversation into the model. While we focused our study
on controversial political and societal topics, additional work is needed to
ensure the model generalizes to more mundane topics, since the signals leading
towards a personal attack could be very different for these conversations.

While our model performed impressively in regards to our test data, we are
confident that future work could further improve performance of the model. Our
model could be improved by addressing all the sources of loss mentioned
earlier. Giving the model a sense of nuanced language by appending an
attention head for detecting the 6 attributes of unhealthy conversations as
noted in Price et al. would do well to address this deficiency. Another clear
area of improvement, as referenced earlier, would be to communicate the
sentiment of GIFs as input to the model. Finally, the robustness of the model
would be greatly improved by anyone with the resources to reliably collect and
accurately tag additional tweets.

As the model becomes more capable, we hope it can become a practical tool to
assist Twitter users to interact with more civility and awareness. Given this
fine-tuned ability to recognize conversations headed for derailment, Twitter
could proactively warn users. We believe that this awareness would allow users
to guide themselves towards a more productive resolution, allowing all parties
involved to have a better, more positive experience.

Figure 3: A mock-up of a conversation warning notification on a sample
conversation.

Github repo: https://github.com/stevendleung/Hashing-It-Out/tree/main

##  7 References

## References

  * 1. J. Ah-Pine and E.-P. Soriano-Morales.  A Study of Synthetic Oversampling for Twitter Imbalanced Sentiment Analysis.  In Workshop on Interactions between Data Mining and Natural Language Processing (DMNLP 2016), Proceedings of the Workshop on Interactions between Data Mining and Natural Language Processing, Riva del Garda, Italy, Sept. 2016.
  * 2. J. P. Chang and C. Danescu-Niculescu-Mizil.  Trouble on the horizon: Forecasting the derailment of online conversations as they develop, 2019.
  * 3. P. Charitidis, S. Doropoulos, S. Vologiannidis, I. Papastergiou, and S. Karakeva.  Hate speech and personal attack dataset in English social media, Oct. 2019.
  * 4. N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer.  Smote: Synthetic minority over-sampling technique.  Journal of Artificial Intelligence Research, 16:321–357, Jun 2002.
  * 5. J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
  * 6. J. Howard and S. Ruder.  Universal language model fine-tuning for text classification, 2018.
  * 7. P. Liu, J. Guberman, L. Hemphill, and A. Culotta.  Forecasting the presence and intensity of hostility on instagram using linguistic and social features, 2018.
  * 8. D. Q. Nguyen, T. Vu, and A. T. Nguyen.  Bertweet: A pre-trained language model for english tweets.  2020\.
  * 9. J. Pavlopoulos, P. Malakasiotis, and I. Androutsopoulos.  Deeper attention to abusive user content moderation.  In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1125–1135, Copenhagen, Denmark, Sept. 2017. Association for Computational Linguistics.
  * 10. I. Price, J. Gifford-Moore, J. Fleming, S. Musker, M. Roichman, G. Sylvain, N. Thain, L. Dixon, and J. Sorensen.  Six attributes of unhealthy conversation, 2020.
  * 11. C. Sun, X. Qiu, Y. Xu, and X. Huang.  How to fine-tune bert for text classification?, 2020.
  * 12. G. Tang, M. Müller, A. Rios, and R. Sennrich.  Why self-attention? a targeted evaluation of neural machine translation architectures, 2018.
  * 13. Twitter.  Our approach to policy development and enforcement philosophy.
  * 14. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  CoRR, abs/1706.03762, 2017.
  * 15. T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush.  Huggingface’s transformers: State-of-the-art natural language processing, 2020.
  * 16. E. Wulczyn, N. Thain, and L. Dixon.  Ex machina: Personal attacks seen at scale, 2017.
  * 17. J. Zhang, J. Chang, C. Danescu-Niculescu-Mizil, L. Dixon, Y. Hua, D. Taraborelli, and N. Thain.  Conversations gone awry: Detecting early signs of conversational failure.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1350–1361, Melbourne, Australia, July 2018. Association for Computational Linguistics.


Plugin estimators for selective classification
with out-of-distribution detection

Harikrishna Narasimhan

Google Research, Mountain View

Aditya Krishna Menon

Google Research, New York

Wittawat Jitkrittum

Google Research, New York

Sanjiv Kumar

Google Research, New York

§ INTRODUCTION

§ BACKGROUND AND NOTATION

§ BAYES-OPTIMAL SELECTIVE CLASSIFICATION WITH OOD DETECTION

§ PLUG-IN ESTIMATORS TO THE BAYES-OPTIMAL SCOD RULE

§ EXPERIMENTAL RESULTS

§ DISCUSSION AND FUTURE WORK

§ PROOFS

We first define a joint marginal distribution $\Pcomb$ that samples from $\Pr_{\rm in}(x)$ and $\Pr_{\rm out}(x)$ with equal probabilities.

We then rewrite the objective in (<ref>) in terms of the joint marginal distribution:

\begin{align*}
{L_{\rm scod}(h, r)} &= \Ex_{x \sim \Pcomb}\left[ T_1( h( x ), r( x ) ) + T_2( h( x ), r( x ) ) \right] \\
T_1( h( x ), r( x ) ) &= ( 1 - \costin - \costout ) \cdot \Ex_{y|x \sim \Pr_{\rm in}}\left[\frac{\Pr_{\rm in}(x)}{\Pcomb(x)} \cdot \1( y \neq h( x ), h( x ) \neq \abstain) \right] \\
&= ( 1 - \costin - \costout ) \cdot \sum_{y \in [L]}\Pr_{\rm in}(y|x) \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)} \cdot \1( y \neq h( x ), h( x ) \neq \abstain) \\
T_2( h( x ), r( x ) ) &= \costin \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)} \cdot\1( h( x ) = \abstain ) + + \costout \cdot \1( h( x ) \neq \abstain ).
\end{align*}

The conditional risk that a classifier $h$ incurs when abstaining (i.e., predicting $r( x ) = 1$) on a fixed instance $x$ is given by:

\[
\costin \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)}.
\]

The conditional risk associated with predicting a base class $y \in [L]$ on instance $x$ is given by:

\[
% (1 - \eta_{\rm wild}(x)) \cdot \left(1 - \Pr_{\rm in}(y|x)\right) +
% \eta_{\rm wild}(x) \cdot c_{\rm wild}.
( 1 - \costin - \costout ) \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)} \cdot \left( 1 - \Pr_{\rm in}(y|x) \right)
+ \costout \cdot \frac{\Pr_{\rm out}(x)}{\Pcomb(x)}
\]

The Bayes-optimal classifier then predicts the label with the lowest conditional risk.
When $\Pr_{\rm in}( x ) = 0$, this amounts to predicting abstain ($r( x ) = 1$).
When $\Pr_{\rm in}( x ) > 0$, the optimal classifier predicts $r( x ) = 1$ when:

\begin{align*}
&\costin \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)}
< ( 1 - \costin - \costout ) \cdot \frac{\Pr_{\rm in}(x)}{\Pcomb(x)} \cdot \min_{y \in [L]}\left( 1 - \Pr_{\rm in}(y|x) \right)
+ \costout \cdot \frac{\Pr_{\rm out}(x)}{\Pcomb(x)}
\\
\costin \cdot {\Pr_{\rm in}(x)}
< ( 1 - \costin - \costout ) \cdot {\Pr_{\rm in}(x)} \cdot \min_{y \in [L]}\left( 1 - \Pr_{\rm in}(y|x) \right)
+ \costout \cdot {\Pr_{\rm out}(x)}
\\
% \\
\costin \cdot {\Pr_{\rm in}(x)}
< ( 1 - \costin - \costout ) \cdot {\Pr_{\rm in}(x)} \cdot \left( 1 - \max_{y \in [L]}\Pr_{\rm in}(y|x) \right)
+ \costout \cdot {\Pr_{\rm out}(x)} \\
% \\
\costin
< ( 1 - \costin - \costout ) \cdot \left( 1 - \max_{y \in [L]}\Pr_{\rm in}(y|x) \right)
+ \costout \cdot \frac{\Pr_{\rm out}(x)}{\Pr_{\rm in}(x)}.
\end{align*}

Otherwise, the classifier does not abstain ($r( x ) = 0$),
and predicts $\argmax_{y \in [L]}\, \Pr_{\rm in}(y|x)$, as desired.

Recall that in open-set classification,
the outlier distribution is $\Pr_{\rm out}( x ) = \Pr_{\rm te}(x \mid y=L)$,
the training distribution is

\begin{align*}
\PTr( x \mid y ) &= \mathbb{P}_{\rm te}( x \mid y ) \\
\piTr( y ) &= \Pr_{\rm in}( y ) \\
&= \frac{1( y \neq L )}{1 - \pi_{\rm te}( L )} \cdot \pi_{\rm te}( y ).
\end{align*}

We will find it useful to derive the following quantities.

\begin{align*}
\PTr( x, y ) &= \piTr( y ) \cdot \PTr( x \mid y ) \\
&= \frac{1( y \neq L ) }{1 - \pi_{\rm te}( L )} \cdot \pi_{\rm te}( y ) \cdot \mathbb{P}_{\rm te}( x \mid y ) \\
&= \frac{1( y \neq L ) }{1 - \pi_{\rm te}( L )} \cdot \mathbb{P}_{\rm te}( x, y ) \\
\PTr( x ) &= \sum_{y \in [L]} \PTr( x, y ) \\
&= \sum_{y \in [L]} \piTr( y ) \cdot \PTr( x \mid y ) \\
&= \frac{1}{1 - \pi_{\rm te}( L )} \sum_{y \neq L} \pi_{\rm te}( y ) \cdot \mathbb{P}_{\rm te}( x \mid y ) \\
&= \frac{1}{1 - \pi_{\rm te}( L )} \sum_{y \neq L} \mathbb{P}_{\rm te}( y \mid x ) \cdot \mathbb{P}_{\rm te}( x ) \\
&= \frac{\mathbb{P}_{\rm te}( y \neq L \mid x )}{1 - \pi_{\rm te}( L )} \cdot \mathbb{P}_{\rm te}( x ) \\
\PTr( y \mid x ) &= \frac{\PTr( x, y )}{\PTr( x )} \\
&= \frac{1( y \neq L ) }{1 - \pi_{\rm te}( L )} \cdot \frac{1 - \pi_{\rm te}( L )}{\mathbb{P}_{\rm te}( y \neq L \mid x )} \cdot \frac{\mathbb{P}_{\rm te}( x, y )}{\mathbb{P}_{\rm te}( x )}  \\
&= \frac{1( y \neq L )}{\mathbb{P}_{\rm te}( y \neq L \mid x )} \cdot \mathbb{P}_{\rm te}( y \mid x ).
\end{align*}

The first part follows from standard results in cost-sensitive learning <cit.>:

\begin{align*}
r^*(x) = 1
\costin \cdot \Pr_{\rm in}( x ) - \costout \cdot \Pr_{\rm out}( x ) < 0 \\
\costin \cdot \Pr_{\rm in}( x ) < \costout \cdot \Pr_{\rm out}( x ) \\
\costin \cdot \Pr_{\rm te}( x \mid y \neq L ) < \costout \cdot \Pr_{\rm te}( x \mid y = L ) \\
\costin \cdot \Pr_{\rm te}( y \neq L \mid x ) \cdot \Pr_{\rm te}( y = L ) < \costout \cdot \Pr_{\rm te}( y = L \mid x ) \cdot \Pr_{\rm te}( y \neq L ) \\
\frac{\costin \cdot \Pr_{\rm te}( y = L )}{\costout \cdot \Pr_{\rm te}( y \neq L )} < \frac{\Pr_{\rm te}( y = L \mid x )}{\Pr_{\rm te}( y \neq L \mid x )} \\
\mathbb{P}_{\rm te}( y = L \mid x ) > F\left( \frac{\costin \cdot \Pr_{\rm te}( y = L )}{\costout \cdot \Pr_{\rm te}( y \neq L )} \right).
% \mathbb{P}_{\rm te}( y = L \mid x ) > \frac{ \costin }{ \costin + \costout} \\
\end{align*}

We further have for threshold $t^*_{\rm osc} \defEq F\left( \frac{\costin \cdot \Pr_{\rm te}( y = L )}{\costout \cdot \Pr_{\rm te}( y \neq L )} \right)$,

\begin{align*}
\mathbb{P}_{\rm te}( y = L \mid x ) \geq t^*_{\rm osc} &\iff \mathbb{P}_{\rm te}( y \neq L \mid x ) \leq 1 - t^*_{\rm osc} \\
&\iff \frac{1}{\mathbb{P}_{\rm te}( y \neq L \mid x )} \geq \frac{1}{1 - t^*_{\rm osc}} \\
&\iff \frac{\max_{y' \neq L} \mathbb{P}_{\rm te}( y' \mid x)}{\mathbb{P}_{\rm te}( y \neq L \mid x )} \geq \frac{\max_{y' \neq L} \mathbb{P}_{\rm te}( y' \mid x)}{1 - t^*_{\rm osc}} \\
&\iff \max_{y' \neq L} \PTr( y' \mid x ) \geq \frac{\max_{y' \neq L} \mathbb{P}_{\rm te}( y' \mid x)}{1 - t^*_{\rm osc}}.
\end{align*}

That is, we want to reject when the maximum softmax probability is higher than some (sample-dependent) threshold.

Fix $\epsilon \in (0,1)$.
We consider two cases for threshold $t_{\rm msp}$:

Case (i): $t_{\rm msp} \leq \frac{1}{L-1}$. Consider a distribution where for all instances $x$, $\mathbb{P}_{\rm te}( y = L \mid x ) = 1 - \epsilon$ and $\mathbb{P}_{\rm te}( y' \mid x) = \frac{\epsilon}{L-1}, \forall y' \ne L$. Then the Bayes-optimal classifier  accepts any instance $x$ for all thresholds $t \in \big(0, 1-\epsilon\big)$. In contrast, Chow's rule would compute $\max_{y \ne L}\PTr( y \mid x) = \frac{1}{L-1},$ and thus reject all instances $x$.

Case (ii): $t_{\rm msp} > \frac{1}{L-1}$. Consider a distribution where for all instances $x$, $\mathbb{P}_{\rm te}( y = L \mid x ) = \epsilon$ and $\mathbb{P}_{\rm te}( y' \mid x) = \frac{1-\epsilon}{L-1}, \forall y' \ne L$. Then the Bayes-optimal classifier would reject any instance $x$ for thresholds $t \in \big(\epsilon, 1\big)$, whereas Chow's rule would accept all instances.

Taking $\epsilon \rightarrow 0$ completes the proof.

Let $\Pr^*$ denote the joint distribution that draws a sample from $\Pr_{\rm in}$ and $\Pr_{\rm out}$ with equal probability. Denote $\gamma_{\rm in}(x) = \frac{ \Pr_{\rm in}(x) }{ \Pr_{\rm in}(x) + \Pr_{\rm out}(x) }$.

The joint risk in (<ref>) can be written as:

\begin{align*}
\lefteqn{L_{\rm scod}(h, r) }\\
(1 - \costin - \costout) \cdot \Pr_{\rm in}( y \neq {h}( x ), r( x ) = 0 ) +
\costin \cdot \Pr_{\rm in}( r( x ) = 1 ) + \costout \cdot \Pr_{\rm out}( r( x ) = 0 )\\
\Ex_{x \sim \Pr^*}\Big[ (1 - \costin - \costout) \cdot \gamma_{\rm in}(x)
\cdot
\sum_{y \ne h(x)} \Pr_{\rm in}( y \mid x) \cdot \1( r( x ) = 0 )  \\[-5pt]
& \hspace{3.5cm} +
\costin \cdot \gamma_{\rm in}(x) \cdot \1( r( x ) = 1 )
+ \costout \cdot (1 - \gamma_{\rm in}(x)) \cdot \1( r( x ) = 0 ) \Big].
\end{align*}

For class probability estimates $\hat{\Pr}_{\rm in}(y \mid x) \approx \Pr_{\rm in}(y \mid x)$, and scorers
$\hat{s}_{\rm sc}(x) = \max_{y \in [L]} \hat{\Pr}_{\rm in}(y \mid x)$ and
$\hat{s}_{\rm ood}(x) \approx \frac{ \Pr_{\rm in}(x) }{ \Pr_{\rm out}(x)}$, we construct a classifier $\hat{h}(x) \in \argmax_{y \in [L]} \hat{\eta}_y(x)$ and black-box rejector:

\begin{equation}
\label{eqn:plug-in-black-box-rewritten}
\hat{r}_{\rm BB}( x ) = 1 \iff ( 1 - \costin - \costout ) \cdot (1 - \hat{s}_{\rm sc}( x )) + {\costout} \cdot \left( \frac{ 1 }{ \hat{s}_{\rm ood}( x ) } \right) > c_{\rm in}.
\end{equation}

Let $(h^*, r^*)$ denote the optimal classifier and rejector as defined in (<ref>).
We then wish to bound the following regret:

\begin{align*}
L_{\rm scod}(\hat{h}, \hat{r}_{\rm BB}) - L_{\rm scod}(h^*, r^*) &=
\underbrace{L_{\rm scod}(\hat{h}, \hat{r}_{\rm BB}) - L_{\rm scod}(h^*, \hat{r}_{\rm BB})}_{ \text{term}_1 } + \underbrace{L_{\rm scod}(h^*, \hat{r}_{\rm BB}) - L_{\rm scod}(h^*, r^*)}_{ \text{term}_2 }.
\end{align*}

We first bound the first term:

\begin{align*}
\text{term}_1 &=
\Ex_{x \sim \Pr^*}\left[ (1 - \costin - \costout) \cdot \gamma_{\rm in}(x)
\cdot \1( \hat{r}_{\rm BB}( x ) = 0 ) \cdot
\Big( \sum_{y \ne \hat{h}(x)} \Pr_{\rm in}( y \mid x)
- \sum_{y \ne h^*(x)} \Pr_{\rm in}( y \mid x) \Big)
\right] \\
&=  \Ex_{x \sim \Pr^*}\left[ \omega(x) \cdot
\Big( \sum_{y \ne \hat{h}(x)} \Pr_{\rm in}( y \mid x)
- \sum_{y \ne h^*(x)} \Pr_{\rm in}( y \mid x) \Big)
\right],
\end{align*}

where we denote $\omega(x) = (1 - \costin - \costout) \cdot \gamma_{\rm in}(x)
\cdot \1( \hat{r}_{\rm BB}( x ) = 0 )$.

Furthermore, we can write:

\begin{align*}
\lefteqn{\text{term}_1}\\
% &=
% \Ex_{x \sim \Pr^*}\left[ \omega(x) \cdot
% \Big( \sum_{y \ne \hat{h}(x)} \Pr_{\rm in}( y \mid x)
% - \sum_{y \ne h^*(x)} \Pr_{\rm in}( y \mid x) \Big)
%  \right] \\
\Ex_{x \sim \Pr^*}\left[ \omega(x) \cdot
\Big( \sum_{y \ne \hat{h}(x)} \Pr_{\rm in}( y \mid x)
\sum_{y \ne h^*(x)} \hat{\Pr}_{\rm in}( y \mid x)
\sum_{y \ne h^*(x)} \hat{\Pr}_{\rm in}( y \mid x)
- \sum_{y \ne h^*(x)} \Pr_{\rm in}( y \mid x) \Big)
\right] \\
\Ex_{x \sim \Pr^*}\left[ \omega(x) \cdot
\Big( \sum_{y \ne \hat{h}(x)} \Pr_{\rm in}( y \mid x)
\sum_{y \ne \hat{h}(x)} \hat{\Pr}_{\rm in}( y \mid x)
\sum_{y \ne h^*(x)} \hat{\Pr}_{\rm in}( y \mid x)
- \sum_{y \ne h^*(x)} \Pr_{\rm in}( y \mid x) \Big)
\right]\\
2 \cdot \Ex_{x \sim \Pr^*}\left[ \omega(x) \cdot
\sum_{y  \in [L]}
\left| \Pr_{\rm in}( y \mid x)
\hat{\Pr}_{\rm in}( y \mid x) \right|
\right]\\
2 \cdot \Ex_{x \sim \Pr^*}\left[
\sum_{y  \in [L]}
\left| \Pr_{\rm in}( y \mid x)
\hat{\Pr}_{\rm in}( y \mid x) \right|
\right],
\end{align*}

where the third step uses the definition of $\hat{h}$ and the fact that $\omega(x) > 0$; the last step uses the fact that $\omega(x) \leq 1$.

We bound the second term now. For this, we first define:

\begin{align*}
L_{\rm rej}(r)
\Ex_{x \sim \Pr^*}\bigg[
\left(
(1 - \costin - \costout) \cdot \gamma_{\rm in}(x) \cdot ( 1 - \max_{y \in [L]} \Pr_{\rm in}(y \mid x) ) + \costout \cdot (1 - \gamma_{\rm in}(x)) \right) \cdot \1(r(x) = 0)\\
& \hspace{10cm}
+ \costin \cdot \gamma_{\rm in}(x) \cdot \1(r(x) = 1) \bigg].
\end{align*}

\begin{align*}
{ \hat{L}_{\rm rej}(r)  }
\Ex_{x \sim \Pr^*}\bigg[
\left(
(1 - \costin - \costout) \cdot \hat{\gamma}_{\rm in}(x) \cdot ( 1 - \max_{y \in [L]} \hat{\Pr}_{\rm in}(y \mid x) ) + \costout \cdot (1 - \hat{\gamma}_{\rm in}(x)) \right) \cdot \1(r(x) = 0)\\
& \hspace{10cm}
+ \costin \cdot \hat{\gamma}_{\rm in}(x) \cdot \1(r(x) = 1) \bigg],
\end{align*}

where we denote $\hat{\gamma}_{\rm in}(x) = \frac{\hat{s}_{\rm ood}(x)}{1 + \hat{s}_{\rm ood}(x)}$.

Notice that $r^*$ minimizes $L(r)$ over all rejectors $r: \mathcal{X} \rightarrow \{0, 1\}$. Similarly, note that $\hat{r}_{\rm BB}$ minimizes $\hat{L}(r)$ over all rejectors $r: \mathcal{X} \rightarrow \{0, 1\}$.

Then the second term can be written as:

\begin{align*}
\text{term}_2
L_{\rm rej}(\hat{r}_{\rm BB}) - L_{\rm rej}(r^*)\\
&=  L_{\rm rej}(\hat{r}_{\rm BB}) -
\hat{L}_{\rm rej}(r^*)
\hat{L}_{\rm rej}(r^*)
L_{\rm rej}(r^*)
\\
L_{\rm rej}(\hat{r}_{\rm BB}) -
\hat{L}_{\rm rej}(\hat{r}_{\rm BB})
\hat{L}_{\rm rej}(r^*)
L_{\rm rej}(r^*)\\
2 \cdot(1 - \costin - \costout) \cdot  \left|\max_{y \in [L]} \Pr_{\rm in}(y \mid x) - \max_{y \in [L]} \hat{\Pr}_{\rm in}(y \mid x) \right|\cdot|\gamma_{\rm in}(x) - \hat{\gamma}_{\rm in}(x)|\\
\hspace{6cm}+
2 \cdot \big(
(1 - \costin - \costout)   + \costout + \costin \big) \cdot |\gamma_{\rm in}(x) - \hat{\gamma}_{\rm in}(x)|
\\
&\leq 2 \cdot(1 - \costin - \costout) \cdot  (1) \cdot|\gamma_{\rm in}(x) - \hat{\gamma}_{\rm in}(x)| +
2 \cdot  (1) \cdot|\gamma_{\rm in}(x) - \hat{\gamma}_{\rm in}(x)|
\\
&\leq 4 \cdot |\gamma_{\rm in}(x) - \hat{\gamma}_{\rm in}(x)|\\
&= 4 \cdot \left|
\frac{ \Pr_{\rm in}(x) }{ \Pr_{\rm in}(x) + \Pr_{\rm out}(x) } - \frac{\hat{s}_{\rm ood}(x)}{1 + \hat{s}_{\rm ood}(x)}
\right|,
\end{align*}

where the third step follows from $\hat{r}_{\rm BB}$ being a minimizer of $\hat{L}_{\rm rej}(r)$, the fourth step uses the fact that $\left|\max_{y \in [L]} \Pr_{\rm in}(y \mid x) - \max_{y \in [L]} \hat{\Pr}_{\rm in}(y \mid x) \right| \leq 1$, and the fifth step uses the fact that $c_{\rm in} + c_{\rm out} \leq 1$.

Combining the bounds on $\text{term}_1$ and $\text{term}_2$ completes the proof.

We first note that $f^*(x) \propto \log(\mathbb{P}_{\rm in}(y \mid x))$ and $s^*(x) = \log\big( \frac{ \mathbb{P}^*(z = 1 \mid x) }{ \mathbb{P}^*(z = 0 \mid x) } \big)$.

Regret Bound 1: We start with the first regret bound. We expand the multi-class cross-entropy loss to get:

\begin{align*}
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f( x ) )
\right]  &=
\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[ -\sum_{y \in [L]} \mathbb{P}_{\rm in}(y \mid x) \cdot \log\left( p_y( x ) \right)
\right] \\
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f^*( x ) )
\right]  &=
\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[ -\sum_{y \in [L]} \mathbb{P}_{\rm in}(y \mid x) \cdot \log\left( \mathbb{P}_{\rm in}(y \mid x) \right)
\right].
\end{align*}

The right-hand side of the first bound can then be expanded as:

\begin{align}
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f( x ) )
\right] -
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f^*( x ) )
\right]
\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[ \sum_{y \in [L]} \mathbb{P}_{\rm in}(y \mid x) \cdot \log\left( \frac{ \mathbb{P}_{\rm in}(y \mid x) }{ p_y( x ) } \right)
\right],
\label{eqn:kl-rewritten}
\end{align}

which the KL-divergence between $\mathbb{P}_{\rm in}(y \mid x) $ and $p_y(x)$.

The KL-divergence between two probability mass functions $p$ and $q$ over $\mathcal{U}$ can be lower bounded by:

\begin{equation}
\text{KL}(p || q) \geq \frac{1}{2} \left( \sum_{u \in \mathcal{U}} |p(u) - q(u)| \right)^2.
\label{eqn:kld-bound}
\end{equation}

Applying (<ref>) to (<ref>), we have:

\begin{align*}
\sum_{y \in [L]} \mathbb{P}_{\rm in}(y \mid x) \cdot \log\left( \frac{ \mathbb{P}_{\rm in}(y \mid x) }{ p_y( x ) } \right)
\frac{1}{2}\left(
\sum_{y \in [L]} \left|\mathbb{P}_{\rm in}(y \mid x) -  p_y( x ) \right|
\right)^2,
\end{align*}

and therefore:

\begin{align*}
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f( x ) )
\right] -
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f^*( x ) )
\right]
\frac{1}{2}\cdot\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[ \left(
\sum_{y \in [L]} \left|\mathbb{P}_{\rm in}(y \mid x) -  p_y( x ) \right|
\right)^2
\right] \\
\frac{1}{2}
\left(
\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[
\sum_{y \in [L]} \left|\mathbb{P}_{\rm in}(y \mid x) -  p_y( x ) \right|
\right]
\right)^2,
\end{align*}

\[
\mathbb{E}_{x \sim \mathbb{P}_{\rm in}}\left[
\sum_{y \in [L]} \big|
\Pr_{\rm in}(y \mid x) - p_y(x) \big| \right]
\leq
\sqrt{2}\sqrt{
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f( x ) )
\right]
\,-\,
\mathbb{E}_{( x, y ) \sim \mathbb{P}_{\rm in}}\left[ \ell_{\rm mc}( y, f^*( x ) )
\right]
\]

Regret Bound 2: We expand the binary  sigmoid cross-entropy loss to get:

\begin{align*}
\mathbb{E}_{( x, z ) \sim \mathbb{P}^*}\left[ \ell_{\rm bc}(z , s( x ) )\right]
\mathbb{E}_{x \sim \mathbb{P}^*}\left[ -\mathbb{P}^*(z = 1 \mid x) \cdot \log\left( p_\perp( x ) \right)
\,-\,
\mathbb{P}^*(z = -1 \mid x) \cdot \log\left( 1 - p_\perp( x ) \right)
\right]\\
\mathbb{E}_{( x, z ) \sim \mathbb{P}^*}\left[ \ell_{\rm bc}(z , s^*( x ) )\right]
\mathbb{E}_{x \sim \mathbb{P}^*}\left[ -\mathbb{P}^*(z = 1 \mid x) \cdot \log\left( \mathbb{P}^*(z = 1 \mid x) \right)
\,-\,
\mathbb{P}^*(z = -1 \mid x) \cdot \log\left( \mathbb{P}^*(z = -1 \mid x) \right)
\right],
\end{align*}

and furthermore

\begin{align*}
\lefteqn{
\mathbb{E}_{( x, z ) \sim \mathbb{P}^*}\left[ \ell_{\rm bc}( z, s( x ) )
\right]
\,-\,
\mathbb{E}_{( x, z ) \sim \mathbb{P}^*}\left[ \ell_{\rm bc}(z , s^*( x ) )\right]}\\
\mathbb{E}_{x \sim \mathbb{P}^*}\left[
\mathbb{P}^*(z = 1 \mid x) \cdot \log\left( \frac{ \mathbb{P}^*(z = 1 \mid x) }{ p_\perp(x) } \right) \,+\,
\mathbb{P}^*(z = -1 \mid x) \cdot \log\left( \frac{ \mathbb{P}^*(z = -1 \mid x) }{ 1 - p_\perp(x) } \right)
\right]
\\
\geq
\mathbb{E}_{x \sim \mathbb{P}^*}\left[
\frac{1}{2}\left( |\mathbb{P}^*(z = 1 \mid x) - p_\perp(x)| +  |\mathbb{P}^*(z = -1 \mid x) - (1 - p_\perp(x))|\right)^2
\right]
\\
\mathbb{E}_{x \sim \mathbb{P}^*}\left[
\frac{1}{2}\left( |\mathbb{P}^*(z = 1 \mid x) - p_\perp(x)| +  |(1 - \mathbb{P}^*(z = 1 \mid x)) - (1 - p_\perp(x))|\right)^2
\right]
\\
\mathbb{E}_{x \sim \mathbb{P}^*}\left[
|\mathbb{P}^*(z = 1 \mid x) - p_\perp(x)|^2
\right]\\
2\cdot \left(\mathbb{E}_{x \sim \mathbb{P}^*}\left[
|\mathbb{P}^*(z = 1 \mid x) - p_\perp(x)|
\right]\right)^2,
\end{align*}

where the second step uses the bound in (<ref>) and the last step uses Jensen's inequality. Taking square-root on both sides and noting that $\mathbb{P}^*(z = 1 \mid x) = \frac{\Pr_{\rm in}( x )}{\Pr_{\rm in}( x ) + \Pr_{\rm out}( x )}$ completes the proof.

§ TECHNICAL DETAILS: COUPLED LOSS

Our second loss function
seeks to learn an augmented scorer $\bar{f} \colon \XCal \to \Real^{L+1}$, with the additional score corresponding to a “reject class”, denoted by $\perp$, and is based on the following simple observation:

$$ z_{y'}( x ) = \begin{cases}
(1 - \costin - \costout) \cdot \Pr_{\rm in}( y \mid x ) & \text{ if } y' \in [ L ] \\
(1 - 2 \cdot \costin - \costout) + \costout \cdot \frac{\Pr_{\rm out}( x )}{\Pr_{\rm in}( x )} & \text{ if } y' = \perp,
\end{cases} $$

and let
$\zeta_{y'}( x ) = \frac{ z_{y'}( x ) }{ Z( x ) }$
$Z( x ) \defEq {\sum_{y'' \in [ L ] \cup \{ \perp \}} z_{y''}( x ) }$.
Now suppose that one has an estimate
$\hat{\zeta}$ of $\zeta$.
This yields an alternate plug-in estimator of the Bayes-optimal SCOD rule (<ref>):

\begin{equation}
\label{eqn:reject-coupled}
\hat{r}( x ) = 1 \iff \max_{y' \in [L]} \hat{\zeta}_{y'}( x ) < \hat{\zeta}_{\perp}( x ).
\end{equation}

One may readily estimate
with a standard multi-class loss $\ell_{\rm mc}$,
with suitable modification:

\begin{equation}
\label{eqn:css-surrogate-repeat}
\E{(x,y) \sim \Pr_{\rm in}}{ \ell_{\rm mc}( y, \bar{f}( x ) ) } + (1 - \costin) \cdot \E{x \sim \Pr_{\rm in}}{ \ell_{\rm mc}( \perp, \bar{f}( x ) ) } + \costout \cdot \E{x \sim \Pr_{\rm out}}{ \ell_{\rm mc}( \perp, \bar{f}( x ) ) }.
\end{equation}

Compared to the decoupled loss (<ref>), the key difference is that the penalties on the rejection logit $\bar{f}_\perp( x )$ involve the classification logits as well.

§ TECHNICAL DETAILS: ESTIMATING THE OOD MIXING WEIGHT $\PI_{\RM MIX}$

To obtain the latter,
we apply a simple transformation as follows.

$\Pr_{\rm mix} = \pi_{\rm mix} \cdot \Pr_{\rm in} + (1-\pi_{\rm mix}) \cdot \Pr_{\rm out}$ with $\pi_{\rm mix} < 1$.
if $\Pr_{\rm in}( x ) > 0$,

\frac{ \Pr_{\rm out}(x) }{ \Pr_{\rm in}(x) } =  \frac{1}{1-\pi_{\rm mix}} \cdot \left( \frac{ \Pr_{\rm mix}(x) }{ \Pr_{\rm in}(x) } - \pi_{\rm mix} \right).

The above transformation requires knowing the mixing proportion $\pi_{\rm mix}$ of inlier samples in the unlabeled dataset.

However, as it measures the fraction of OOD samples during deployment,
$\pi_{\rm mix}$ is typically unknown.
We may however estimate this with (A2).
Observe that for a strictly inlier example $x \in S^*_{\rm in}$,
we have $\frac{ \Pr_{\rm mix}(x) }{ \Pr_{\rm in}(x)} = \pi_{\rm mix}$, i.e., $\exp( -\hat{s}(x) ) \approx \pi_{\rm mix}$.
Therefore, we can estimate

\begin{align*}
\hat{s}_{\rm ood}(x) = \left(\frac{1}{1-\hat{\pi}_{\rm mix}} \cdot \left( \exp( -\hat{s}(x) ) - \hat{\pi}_{\rm mix} \right)\right)^{-1}
\quad
\text{where}
\quad
\hat{\pi}_{\rm mix} = \frac{1}{|S^*_{\rm in}|}\sum_{x \in S^*_{\rm in}} \exp(-\hat{s}(x)).
\end{align*}

We remark here that this problem is roughly akin to class prior estimation for PU learning <cit.>,
and noise rate estimation for label noise <cit.>.
As in those literatures,
estimating $\pi_{\rm mix}$ without any assumptions is challenging.
Our assumption on the existence of a Strict Inlier set $S^*_{\rm in}$ is analogous to assuming the existence of a golden label set in the label noise literature <cit.>.

Expanding the right-hand side, we have:

\begin{align*}
\frac{1}{1-\pi_{\rm mix}} \cdot \left( \frac{ \Pr_{\rm mix}(x) }{ \Pr_{\rm in}(x) } - \pi_{\rm mix} \right)
&= \frac{1}{1-\pi_{\rm mix}} \cdot \left( \frac{ \pi_{\rm mix} \cdot \Pr_{\rm in}(x) + (1-\pi_{\rm mix}) \cdot \Pr_{\rm out}(x) }{ \Pr_{\rm in}(x) } - \pi_{\rm mix} \right)\\
&= \frac{ \Pr_{\rm out}(x) }{ \Pr_{\rm in}(x) },
\end{align*}

as desired.

§ TECHNICAL DETAILS: PLUG-IN ESTIMATORS WITH AN ABSTENTION BUDGET

Observe that (<ref>) is equivalent to solving the Lagrangian:

\begin{align}
\label{eqn:budget-constrainted-ood}
\min_{h, r} \max_{\lambda} \left[ F( h, r; \lambda ) \right]& \\
\nonumber
F( h, r; \lambda ) \defEq ( 1 - \costFN ) \cdot \Pr_{\rm in}( y \neq {h}( x ), r( x ) = 0 ) & +
\costin(\lambda) \cdot \Pr_{\rm out}( {r}( x ) = 0 ) +
\costout(\lambda) \cdot \Pr_{\rm in}( r( x ) = 1 ) +
\nu_\lambda
\\
\nonumber
\left( \costin(\lambda), \costout(\lambda), \nu_\lambda \right) \defEq ( \costFN - \lambda \cdot (1 - \pi^*_{\rm in}),
\lambda \cdot \pi^*_{\rm in}, \lambda \cdot (1 - \pi^*_{\rm in}) - \lambda \cdot b_{\rm rej} ).
%  \costin(\lambda) &\defEq ( \costFN - \lambda \cdot (1 - \pi^*_{\rm in}) ) \\
%  \nonumber
%  \costout(\lambda) &\defEq \lambda \cdot \pi^*_{\rm in} \\
%  \nonumber
%  \gamma_\lambda &\defEq \lambda \cdot (1 - \pi^*_{\rm in}) - \lambda \cdot b_{\rm rej}.
\end{align}

Solving (<ref>) requires optimising over both $(h, r)$ and $\lambda$.
Suppose momentarily that $\lambda$ is fixed.
Then, $F( h, r; \lambda )$ is exactly a scaled version of
the soft-penalty objective (<ref>).
we can use Algorithm <ref> to construct a plug-in classifier that minimizes the above joint risk.
To find the optimal $\lambda$,
we only need to implement the surrogate minimisation step in Algorithm <ref> once to estimate the relevant probabilities.
We can then construct multiple
plug-in classifiers for different values of $\lambda$,
and perform an inexpensive threshold search:
amongst the classifiers satisfying the budget constraint,
we pick
the one that minimises (<ref>).

The above requires estimating $\pi^*_{\rm in}$, the fraction of inliers observed during deployment.
Following (A2), one plausible estimate is $\pi_{\rm mix}$, the fraction of inliers in the “wild” mixture set $S_{\rm mix}$.

Remark. The previous work of <cit.> for OOD detection also seeks to solve an optimization problem with explicit constraints on abstention rates.
However, there are some subtle, but important, technical differences between their formulation and ours.

Like us, <cit.> also seek to jointly learn a classifier and an OOD scorer, with  constraints  on the classification and abstention rates, given access to samples from $\Pr_{\rm in}$ and $\Pr_{\rm mix}$.

For a joint classifier $h: \XCal \rightarrow [L]$ and rejector $r: \XCal \rightarrow \{0, 1\}$, their formulation can be written as:

\begin{align}
\lefteqn{
\min_{h}~
\Pr_{\rm out}\left( r(x) = 0 \right) }
\label{eq:ks-original}
\\
\text{s.t.}\hspace{20pt}
& \Pin\left( r(x) = 1 \right) \leq \kappa
\nonumber
\\
& \Pin\left( {h}(x) \ne y,\, r(x) = 0 \right)  \leq \tau,
\nonumber
\end{align}

for given targets $\kappa, \tau \in (0,1)$.

While $\Pr_{\rm out}$ is not directly available,
provide a simple solution to solving  (<ref>) using only access to $\Pr_{\rm mix}$ and $\Pr_{\rm in}$. They show that under some mild assumptions,  replacing  $\Pr_{\rm out}$ with $\Pr_{\rm mix}$ in the above problem does not alter the optimal solution. The intuition behind this is that when the first constraint on the inlier abstention rate is satisfied with equality, we have $\Pr_{\rm mix}\left( r(x) = 0 \right) = \pi_{\rm mix} \cdot (1 - \costin) + (1 - \pi_{\rm mix}) \cdot \Pr_{\rm out}\left( r(x) = 0 \right)$, and minimizing this objective is equivalent to minimizing the OOD objective in (<ref>).

This simple trick of replacing $\Pr_{\rm out}$ with $\Pr_{\rm mix}$ will only work when we have an explicit constraint on the inlier abstention rate, and will not work for the formulation we are interested in (<ref>). This is because in our formulation, we impose a budget on the overall abstention rate (as this is a more intuitive quantity that a practitioner may want to constraint), and do not explicitly control the abstention rate on $\Pr_{\rm in}$.

In comparison to <cit.>, the plug-in based approach we prescribe is more general, and can be applied to optimize any objective that involves as a weighted combination of the mis-classification error and the abstention rates on the inlier and OOD samples. This includes both the  budget-constrained problem we consider in (<ref>), and the constrained problem of  in (<ref>).

§ TECHNICAL DETAILS: RELATION OF PROPOSED LOSSES TO EXISTING LOSSES

Equation <ref> generalises
several existing proposals in the SC and OOD detection literature.
In particular,
reduces to the

loss proposed in <cit.>,
when $\Pr_{\rm in} = \Pr_{\rm out}$,
i.e., when one only wishes to abstain on low confidence ID samples.
this also corresponds to the decoupled loss
for OOD detection
in <cit.>;
crucially, however,

reject only based on whether $\bar{f}_{\perp}( x ) < 0$,
rather than comparing $\bar{f}_{\perp}( x )$ and $\max_{y' \in [L]} \bar{f}_{y'}( x )$.
The latter is essential to match the Bayes-optimal predictor in (<ref>).
the coupled loss in (<ref>) reduces to the
cost-sensitive softmax cross-entropy
in <cit.>
when $\costout = 0$,
and the OOD detection
loss of <cit.> when $\costin = 0, \costout = 1$.

§ ADDITIONAL EXPERIMENTS

We provide details about the hyper-parameters and dataset splits used in the experiments, as well as, additional experimental results and plots that were not included in the main text. The in-training experimental results are averaged over 5 random trials.

§.§ Hyper-parameter choices

We provide details of the learning rate (LR) schedule and other hyper-parameters used in our experiments.

Dataset     Model     LR     Schedule     Epochs     Batch sizeCIFAR-40/100
CIFAR ResNet 56     1.0     anneal     256     1024

We use SGD with momentum as the optimization
algorithm for all models. For annealing schedule, the specified learning
rate (LR) is the initial rate, which is then decayed by a factor of
ten after each epoch in a specified list. For CIFAR, these epochs
are 15, 96, 192 and 224.

§.§ Baseline details

We provide further details about the baselines we compare with. The following baselines are trained on only the inlier data.

* MSP or Chow's rule: Train a scorer $f: \cX \rightarrow \R^L$ using CE loss, and threshold the MSP
to decide to abstain <cit.>.

* MaxLogit: Same as above, but instead threshold the maximum logit $\max_{y \in [L]} f_y(x)$  <cit.>.

* Energy score: Same as above, but threshold the energy function $-\log\sum_y \exp(f_y(x))$

* ODIN: Train a scorer $f: \cX \rightarrow \R^L$ using CE loss, and uses a combination of input noise and temperature-scaled MSP to decide when to abstain <cit.>.

* SIRC: Train a scorer $f: \cX \rightarrow \R^L$ using CE loss, and compute a post-hoc deferral rule that combines the MSP score with either the $L_1$-norm or the residual score of the embedding layer from the scorer $f$ <cit.>.

* CSS: Minimize the cost-sensitive softmax L2R loss of <cit.> using only the inlier dataset to learn a scorer $f \colon \XCal \to \Real^{L + 1}$, augmented with a rejection score $f_\perp( x )$, and abstain iff $f_{\perp}( x ) > \max_{y' \in [ L ]} f_{y'}( x ) + t$, for threshold $t$.

The following baselines additional use the unlabeled data containing a mix of inlier and OOD samples.

* Coupled CE (CCE): Train a scorer $f \colon \XCal \to \Real^{L + 1}$, augmented with a rejection score $f_\perp( x )$ by optimizing the CCE loss of <cit.>, and abstain iff $f_{\perp}( x ) > \max_{y' \in [ L ]} f_{y'}( x ) + t$, for threshold $t$.

* De-coupled CE (DCE): Same as above but uses the DCE loss of <cit.> for training.

* Outlier Exposure (OE): Train a scorer using the OE loss of <cit.> and threshold the MSP.

§.§ Data split details

For the CIFAR-100 experiments
where we use a wild sample containing a mix of ID and OOD examples, we split the original CIFAR-100 training set into two halves, use one half as the inlier sample and the other half to construct the wild sample. For evaluation, we combine the orignal CIFAR-100 test set with the respective OOD test set. In each case, the larger of the ID and OOD dataset is down-sampled to match the desired ID-OOD ratio. The experimental results are averaged over 5 random trials.

For the pre-trained ImageNet experiments, we sample equal number of examples from the ImageNet validation sample and the OOD dataset, and annotate them with the pre-trained model. The number of samples is set to  the smaller of the size of the OOD dataset or 5000.

§.§ Comparison to CSS and ODIN baselines

We present some representative results in Table <ref> comparing our proposed methods against the cost-sensitive softmax (CSS) of <cit.>, a representative learning-to-reject baseline, and the ODIN method of <cit.>, an OOD detection baseline. As expected, the CSS baseline, which does not have OOD detection capabilities is seen to under-perform. The ODIN, baseline, on the other hand, is occasionally seen to be competitive.

AUC-RC ($\downarrow$) for CIFAR-100 as ID, and a “wild” comprising of 90% ID and only 10% OOD.
The OOD part of the wild set is drawn from the same OOD dataset from which the test set is drawn.
We compare the proposed methods with the cost-sensitive softmax (CSS) learning-to-reject loss of <cit.> and the ODIN method of <cit.>.

We set $c_{\rm fn} = 0.75$.

ID + OOD training with
$\Pr^{\rm tr}_{\rm out} = \Pr^{\rm te}_{\rm out}$

Method / $\Pr^{\rm te}_{\rm out}$     SVHN     Places     OpenImages

CSS     0.286     0.263     0.254

ODIN     0.218     0.217     0.217

Plug-in BB [$L_1$]     0.196     0.210      0.222

Plug-in BB [Res]     0.198     0.236     0.251
Plug-in LB*     0.221     0.199      0.225

§.§ Experimental plots

We present  experimental plots in Figure <ref> of the joint risk in Section <ref> as a function of the fraction of samples abstained. We also plot the inlier accuracy, the OOD precision, and the OOD recall as a function of samples abstained. These metrics are described below:

\begin{align*}
\text{inlier-accuracy}(h, r) &= \frac{
\sum_{(x,y) \in S_{\rm in}}\1(y = \bar{h}(x), r(x) = 0)
\sum_{x \in S_{\rm all}}\1( r(x) = 0 )
\text{ood-precision}(h, r) &= \frac{
\sum_{(x,y) \in S_{\rm out}}\1( r(x) = 1)
\sum_{x \in S_{\rm all}}\1( r(x) = 1)
\text{ood-recall}(\bar{h}) &= \frac{
\sum_{x \in S_{\rm out}}\1( r(x) = 1)
|S_{\rm out}|
\end{align*}

where $S_{\rm all} = \{x: (x, y) \in S_{\rm in}\} \cup S_{\rm out}$ is the combined set of ID and OOD instances.

One can see a few general trends.
The joint risk decreases with more abstentions; the inlier accuracy increases with abstentions.
The OOD precision is the highest initially when the abstentions are on the OOD samples, but decreases when the OOD samples are exhausted, and the abstentions are on the inlier samples; the opposite is true for OOD recall.

[$\Pr_{\rm in}$: CIFAR-100;    $\Pr_{\rm out}$: SVHN]

[$\Pr_{\rm in}$: CIFAR-100;    $\Pr_{\rm out}$: Places365]

[$\Pr_{\rm in}$: CIFAR100;    $\Pr_{\rm out}$: LSUN]

[$\Pr_{\rm in}$: CIFAR-100;    $\Pr_{\rm out}$: Texture]

[$\Pr_{\rm in}$: CIFAR-100;    $\Pr_{\rm out}$: Open Images]

[$\Pr_{\rm in}$: CIFAR-100;    $\Pr_{\rm out}$: CelebA]

Plots of classification and OOD detection metrics as a function of the fraction of abstained samples (averaged over 5 trials). We use CIFAR-100 as the ID sample, and a mix of CIFAR-100 and each of SVHN, Places265, LSUN, LSUN-R, Texture, Open Images and CelebA as the wild sample, and evaluate on the respective OOD dataset. The wild sample contains 90% ID and only 10% OOD samples. The test contains equal proportions of ID and OOD samples. For the joint risk, lower values are better. For all other metrics, higher values are better.

We set $c_{\rm fn} = 0.75$.

§.§ Varying OOD mixing proportion in test set

We repeat the experiments in Table <ref> on CIFAR-100 and 100K Random Images with varying proportions of OOD samples in the test set, and present the results in Table <ref>. One among the proposed plug-in methods continues to perform the best.

Area Under the Risk-Coverage Curve (AUC-RC) for  methods trained with CIFAR-100 as the ID sample and a mix of CIFAR-100 and 300K Random Images as the wild sample, and with the proportion of OOD samples in test set varied.
The wild set contains 10% ID and 90% OOD.

Base model is ResNet-56.
We set $c_{\rm fn} = 0.75$.

A * against a method indicates that it uses both ID and OOD samples for training.
Lower values are better.

Test OOD proportion = 0.25

Test OOD proportion = 0.75

Method / $\Pr^{\rm te}_{\rm out}$      SVHN     Places     LSUN     LSUN-R
Texture            SVHN     Places     LSUN     LSUN-R     Texture

MSP     0.171     0.186     0.176     0.222     0.192
0.501     0.518     0.506     0.564     0.532

MaxLogit     0.156     0.175     0.163     0.204     0.183
0.464     0.505     0.478     0.545     0.512

Energy     0.158     0.177     0.162     0.206     0.181
0.467     0.502     0.477     0.538     0.509
SIRC [$L_1$]     0.158     0.181     0.159     0.218     0.180
0.480     0.513     0.485     0.560     0.509

SIRC [Res]     0.141     0.181     0.152     0.219     0.194
0.456     0.516     0.476     0.561     0.535

CCE*     0.175     0.191     0.153     0.131     0.154
0.460     0.487     0.425     0.374     0.429

DCE*     0.182     0.200     0.155     0.136     0.162
0.467     0.498     0.414     0.372     0.428

OE*     0.179     0.174     0.147     0.117     0.148
0.492     0.487     0.440     0.371     0.440
Plug-in BB [$L_1$]     0.127     0.164     0.128     0.180     0.134
0.395     0.457     0.397     0.448     0.414

Plug-in BB [Res]     0.111     0.175     0.129     0.182     0.248
0.377     0.484     0.407     0.449     0.645

Plug-in LB*     0.160     0.169     0.133     0.099     0.132
0.468     0.489     0.418     0.351     0.430

§.§ Varying OOD cost parameter

We repeat the experiments in Table <ref> on CIFAR-100 and 100K Random Images with varying values of cost parameter $c_{\rm fn}$, and present the results in Table <ref>. One among the proposed plug-in methods continues to perform the best, although the gap between the best and second-best methods increases with $c_{\rm fn}$.

Area Under the Risk-Coverage Curve (AUC-RC) for  methods trained with CIFAR-100 as the ID sample and a mix of CIFAR-100 and 300K Random Images as the wild sample, and for different values of cost parameter $c_{\rm fn}$.
The wild set contains 10% ID and 90% OOD.

Base model is ResNet-56.

$c_{\rm fn} = 0.5$

$c_{\rm fn} = 0.9$

Method / $\Pr^{\rm te}_{\rm out}$      SVHN     Places     LSUN     LSUN-R
Texture            SVHN     Places     LSUN     LSUN-R     Texture

MSP     0.261     0.271     0.265     0.299     0.278
0.350     0.374     0.360     0.448     0.394

MaxLogit     0.253     0.271     0.259     0.293     0.277
0.304     0.350     0.318     0.410     0.360

Energy     0.254     0.273     0.262     0.293     0.277
0.303     0.349     0.317     0.407     0.359
SIRC [$L_1$]     0.252     0.270     0.257     0.298     0.267
0.319     0.368     0.327     0.440     0.358

SIRC [Res]     0.245     0.270     0.251     0.297     0.282
0.286     0.371     0.311     0.440     0.397
CCE*     0.296     0.307     0.283     0.269     0.286
0.282     0.318     0.233     0.179     0.240

DCE*     0.303     0.317     0.285     0.270     0.292
0.289     0.331     0.225     0.177     0.238

OE*     0.287     0.283     0.270     0.255     0.272
0.327     0.315     0.252     0.173     0.251
Plug-in BB [$L_1$]     0.237     0.258     0.239     0.267     0.244
0.207     0.280     0.207     0.266     0.226

Plug-in BB [Res]     0.228     0.266     0.241     0.269     0.321
0.185     0.322     0.218     0.266     0.599

Plug-in LB*     0.256     0.265     0.243     0.222     0.245
0.299     0.326     0.234     0.165     0.246

§.§ Confidence intervals

In Table <ref>, we report 95% confidence intervals for the experiments on CIFAR-100 and 100K Random Images
from Table <ref>. In each case, the differences between the best performing plug-in method and the baselines are statistically significant.

Area Under the Risk-Coverage Curve (AUC-RC) for  methods trained with CIFAR-100 as the ID sample and a mix of CIFAR-100 and 300K Random Images as the wild sample, with 95% confidence intervals included.
The wild set contains 10% ID and 90% OOD.
The test sets contain 50% ID and 50% OOD samples.
Base model is ResNet-56.
We set $c_{\rm fn} = 0.75$.

Method / $\Pr^{\rm te}_{\rm out}$      SVHN     Places     LSUN     LSUN-R

MSP     0.317 $\pm$ 0.023     0.336 $\pm$ 0.010     0.326 $\pm$ 0.005     0.393 $\pm$ 0.018     0.350 $\pm$ 0.004

MaxLogit     0.286 $\pm$ 0.012     0.321 $\pm$ 0.011     0.299 $\pm$ 0.009     0.365 $\pm$ 0.016     0.329 $\pm$ 0.013

Energy     0.286 $\pm$ 0.012     0.320 $\pm$ 0.013     0.296 $\pm$ 0.008     0.364 $\pm$ 0.015     0.326 $\pm$ 0.014
SIRC [$L_1$]     0.294 $\pm$ 0.021     0.331 $\pm$ 0.010     0.300 $\pm$ 0.007     0.387 $\pm$ 0.017     0.326 $\pm$ 0.006

SIRC [Res]     0.270 $\pm$ 0.019     0.332 $\pm$ 0.009     0.289 $\pm$ 0.007     0.384 $\pm$ 0.019     0.353 $\pm$ 0.003

CCE*     0.288 $\pm$ 0.017     0.315 $\pm$ 0.018     0.252 $\pm$ 0.004     0.213 $\pm$ 0.001     0.255 $\pm$ 0.004

DCE*     0.295 $\pm$ 0.015     0.326 $\pm$ 0.028     0.246 $\pm$ 0.004     0.212 $\pm$ 0.001     0.260 $\pm$ 0.005

OE*     0.313 $\pm$ 0.015     0.304 $\pm$ 0.006     0.261 $\pm$ 0.001     0.204 $\pm$ 0.002     0.260 $\pm$ 0.002
Plug-in BB [$L_1$]     0.223 $\pm$ 0.004     0.286 $\pm$ 0.013     0.227 $\pm$ 0.007     0.294 $\pm$ 0.021     0.240 $\pm$ 0.006

Plug-in BB [Res]     0.205 $\pm$ 0.002     0.309 $\pm$ 0.009     0.235 $\pm$ 0.005     0.296 $\pm$ 0.012     0.457 $\pm$ 0.008

Plug-in LB*     0.290 $\pm$ 0.017     0.306 $\pm$ 0.016     0.243 $\pm$ 0.003     0.186 $\pm$ 0.001     0.248 $\pm$ 0.006

§.§ AUC and FPR95 metrics for OOD scorers

Table <ref> reports the AUC-ROC and FPR@95TPR metrics for the OOD scorers used by different methods, treating OOD samples as positives and ID samples as negatives. Note that the CCE, DCE and OE methods which are trained with both ID and OOD samples are seen to perform the best on these metrics. However, this superior performance in OOD detection doesn't often translate to good performance on the SCOD problem (as measured by AUC-RC). This is because these methods abstain solely based on the their estimates of the ID-OOD density ratio, and do not trade-off between accuracy and OOD detection performance.

AUC-ROC (($\uparrow$)) and FPR@95TPR ($\downarrow$) metrics for OOD scorers used by different  methods trained. We use CIFAR-100 as the ID sample and a mix of 50% CIFAR-100 and 50% 300K Random Images as the wild sample.

Base model is ResNet-56.
We set $c_{\rm fn} = 0.75$ in the plug-in methods. The CCE, DCE and OE methods which are trained with both ID and OOD samples are seen to perform the best on these metrics. However, this superior performance in OOD detection doesn't often translate to good performance on the SCOD problem (as measured by AUC-RC in Table <ref>).

OOD AUC-ROC

OOD FPR95

Method / $\Pr^{\rm te}_{\rm out}$      SVHN     Places     LSUN     LSUN-R
Texture            SVHN     Places     LSUN     LSUN-R     Texture

MSP     0.629     0.602     0.615     0.494     0.579
0.813     0.868     0.829     0.933     0.903

MaxLogit     0.682     0.649     0.692     0.564     0.634
0.688     0.846     0.754     0.916     0.864

Energy     0.685     0.654     0.698     0.568     0.645
0.680     0.843     0.742     0.915     0.850
SIRC [$L_1$]     0.699     0.621     0.700     0.516     0.663
0.788     0.871     0.819     0.930     0.882

SIRC [Res]     0.777     0.613     0.735     0.513     0.566
0.755     0.870     0.800     0.929     0.900
CCE*     0.772     0.725     0.878     0.995     0.883
0.647     0.775     0.520     0.022     0.570

DCE*     0.770     0.709     0.905     0.998     0.888
0.693     0.807     0.466     0.007     0.562

OE*     0.699     0.725     0.861     0.998     0.873
0.797     0.792     0.689     0.004     0.706
Plug-in BB [$L_1$]     0.897     0.718     0.896     0.684     0.876
0.473     0.716     0.496     0.717     0.580

Plug-in BB [Res]     0.963     0.667     0.885     0.680     0.432
0.251     0.777     0.559     0.726     0.996

Plug-in LB*     0.710     0.683     0.860     0.997     0.853
0.749     0.801     0.653     0.009     0.697

§.§ Results on CIFAR-40 ID sample

Following  <cit.>, we present in Table <ref> results of experiments where we use CIFAR-40 (a subset of CIFAR-100 with 40 classes) as the ID-only training dataset, and we evaluate on CIFAR-60 (the remainder with 60 classes), SVHN, Places, LSUN and LSUN-R as OOD datasets.

Area Under the Risk-Coverage Curve (AUC-RC) for different methods with CIFAR-40 as the inlier dataset and the training set comprising of only inlier samples, when evaluated on the following OOD datasets: CIFAR60, SVHN, Places, LSUN-C and LSUN-R. The test sets contain 50% ID samples and 50% OOD samples. We set $c_{\rm fn} = 0.75$. The last three rows contain results for the proposed methods.

5cTest OOD dataset

Method     CIFAR60     SVHN     Places     LSUN-C     LSUN-R

MSP     0.262     0.238     0.252     0.282     0.243

MaxLogit     0.272     0.223     0.242     0.252     0.231

Energy     0.266     0.221     0.244     0.248     0.230

SIRC [$\|z\|_1$]     0.263     0.226     0.249     0.266     0.241

SIRC [Res]      0.258     0.209     0.250     0.244     0.241

SIRC [$\|z\|_1$, Bayes-opt]      0.290     0.195     0.243     0.191     0.228

SIRC [Res, Bayes-opt]     0.309     0.175     0.279     0.204     0.247

§.§ Additional results on pre-trained ImageNet models

Following <cit.>, we present additional results with pre-trained models with ImageNet-200 (a subset of ImageNet with 200 classes) as the inlier dataset in Table <ref>. The base model is a ResNet-50.

AUC-RC ($\downarrow$)  for methods trained with ImageNet-200 as the inlier dataset and without OOD samples. The base model is a pre-trained ResNet-50 model.

Lower values are better.

8cID-only training

Method / $\Pr^{\rm te}_{\rm out}$     Places     LSUN     CelebA     Colorectal
iNaturalist-O     Texture
ImageNet-O     Food32

MSP     0.183     0.186     0.156     0.163     0.161     0.172     0.217     0.181

MaxLogit     0.173     0.184     0.146     0.149     0.166     0.162     0.209     0.218

Energy     0.176     0.185     0.145     0.146     0.172     0.166     0.211     0.225

SIRC [$L_1$]     0.185     0.195     0.155     0.165     0.166     0.172     0.214     0.184

SIRC [Res]     0.180     0.179     0.137     0.140     0.151     0.167     0.219     0.174

Plug-in BB [$L_1$]     0.262     0.261     0.199     0.225     0.228     0.270     0.298     0.240

Plug-in BB [Res]     0.184     0.172     0.135     0.138     0.145     0.194     0.285     0.164

4cID-only training

Method / $\Pr^{\rm te}_{\rm out}$     Near-ImageNet-200
Caltech65     Places32     Noise

MSP      0.209     0.184     0.176     0.188

MaxLogit      0.220     0.171     0.170     0.192

Energy      0.217     0.175     0.169     0.190

SIRC [$L_1$]     0.205     0.182     0.174     0.191

SIRC [Res]      0.204     0.177     0.173     0.136

Plug-in BB [$L_1$]      0.264     0.242     0.256     0.344

Plug-in BB [Res]     0.247     0.202     0.171     0.136

§ ILLUSTRATING THE FAILURE OF MSP FOR OOD DETECTION

§.§ Illustration of MSP failure for open-set classification

Figure <ref> shows a graphical illustration of the example discussed in Example <ref>,
wherein the MSP baseline can fail for open-set classification.

Examples of two open-set classification settings (a) and (b) with $L=10$ classes, where the inlier class distributions $\PTr( y \mid x )= \frac{\mathbb{P}_{\rm te}( y \mid x )}{\mathbb{P}_{\rm te}( y \neq 10 \mid x )}$ over the first 9 classes are identical, but the unknown class density $\Pr^*(10|x)$ is significantly different. Consequently, the MSP baseline, which relies only on the inlier class probabilities, will output the same rejection decision for both settings, whereas the Bayes-optimal classifier, which rejects by thresholding $\Pr^*(10|x)$, may output different decisions for the two settings.

[Uniform outlier distribution $\Pr_{\rm out}$.]

[Open-set classification.]

Example of two settings
where the maximum softmax probability (MSP) baseline fails for OOD detection.
Setting (a) considers
low-density OOD detection,
positive and negative samples drawn from a one-dimensional Gaussian distribution.
Samples away from the origin will have $\Pr( x ) \sim 0$,
and are thus outliers under the Bayes-optimal OOD detector.
the MSP baseline will deem
samples near the origin to be outliers,
as these have maximal

$\max_{y} \Pr( y \mid x )$.
This illustrates the distinction between abstentions favoured by L2R
(low label certainty)
OOD detection
(low density).

Setting (b) considers
open-set classification
where there are $L = 4$ total classes, with the fourth class
(denoted by ${\color{red} \blacktriangledown}$)
assumed to comprise outliers not seen during training.
Each class-conditional is an isotropic Gaussian (left).

Note that
the maximum inlier class-probability $\PTr( y \mid x )$ scores OOD samples significantly higher than ID samples (right).
the MSP baseline,
declares samples with low $\max_{y} \PTr( y \mid x )$ as outliers,
will perform poorly.

§.§ Illustration of maximum logit failure for open-set classification

For the same setting as Figure <ref>,
we show
in Figure <ref>
the maximum logit computed over the inlier distribution.
As with the maximum probability, the outlier samples tend to get a higher score than the inlier samples.

For the same reason, rejectors that threshold the margin between the highest and the second-highest probabilities, instead of the maximum class probability, can also fail.
The use of other SC methods such as the cost-sensitive softmax cross-entropy <cit.> may not be successful either, because the optimal solutions for these methods have the same form as MSP.

For the same setting as Figure <ref>,
we show
the maximum logit computed over the inlier distribution.
As with the maximum probability, the outlier samples tend to get a higher score than the inlier samples.

§ ILLUSTRATING THE IMPACT OF ABSTENTION COSTS

§.§ Impact of varying abstention costs $\costin, \costout$

Our joint objective that allows for abstentions on both “hard” and “outlier” samples is controlled by parameters $\costin, \costout$.

These reflect the costs on not correctly abstaining on samples from either class of anomalous sample.
Figure <ref> and <ref> show the impact of varying these parameters while the other is fixed, for the synthetic open-set classification example of Figure <ref>.
The results are intuitive:
varying $\costin$ tends to favour abstaining on samples that are at the class boundaries,
while varying $\costout$ tends to favour abstaining on samples from the outlier class.
Figure <ref> confirms that when both $\costin, \costout$ are varied, we achieve abstentions on both samples at the class boundaries, and samples from the outlier class.

Impact of varying $\costin$ for a fixed $\costout = 0.0$.
The left plot shows the standard dataset, with $\costin = 1.0$.
For intermediate $\costin = 0.5$ (middle), we abstain
(denoting by $\times$)
only on the samples at the class boundaries.
For $\costin = 0.0$ (right), we abstain on all samples.

Impact of varying $\costout$ for a fixed $\costin = 1.0$.
The left plot shows the standard dataset, with $\costout = 0.0$.
For intermediate $\costout = 1.0$ (middle), we abstain
(denoting by $\times$)
only on the samples from the outlier class.
For larger $\costout = 10.0$ (right), we start abstaining on inlier samples as well.

Impact of varying both $\costin$ and $\costout$.
The left plot shows the standard dataset, with $\costin = 1.0, \costout = 0.0$.
Setting $\costin = 0.5, \costout = 1.0$ (middle)
and $\costin = 0.5, \costout = 10.0$ (right)
is shown to favour abstaining
(denoting by $\times$)
on both the samples at class boundaries, and the outlier samples.

§.§ Impact of $\costout$ on OOD Detection Performance

For the same setting as Figure <ref>,
we consider the OOD detection performance of the
$s( x ) = \max_{y \in [L]} \Pr_{\rm in}( y \mid x ) - \costout \cdot \frac{\Pr_{\rm in}( x )}{\Pr_{\rm out}( x )}$
as $\costout$ is varied.
Note that thresholding of this score determines the Bayes-optimal classifier.

Rather than pick a fixed threshold, we use this score to compute the AUC-ROC for detecting whether a sample is from the outlier class, or not.
As expected, as $\costout$ increases
i.e., there is greater penalty on not rejecting an OOD sample
the AUC-ROC improves.

For the same setting as Figure <ref>,
we consider the OOD detection performance of the
score $s( x ) = \max_{y \in [L]} \Pr_{\rm in}( y \mid x ) - \costout \cdot \frac{\Pr_{\rm in}( x )}{\Pr_{\rm out}( x )}$ as $\costout$ is varied.
Specifically, we use this score to compute the AUC-ROC for detecting whether a sample is from the outlier class, or not.
As expected, as $\costout$ increases, the AUC-ROC improves.

§ LIMITATIONS AND BROADER IMPACT

Recall that our proposed plug-in rejectors  seek to optimize for overall classification and OOD detection accuracy while keeping the total fraction of abstentions within a limit. However, the improved overall accuracy may come at the cost of poorer performance on smaller sub-groups. For example, <cit.> show that Chow's rule or the MSP scorer “can magnify existing accuracy disparities between various groups within a population, especially in the presence of spurious correlations”.
It would be of interest to carry out a similar study with the two plug-in based rejectors proposed in this paper, and to  understand how both their inlier classification accuracy and their OOD detection performance varies across sub-groups. It would also be of interest to explore variants of our proposed rejectors that mitigate such disparities among sub-groups.

Another limitation of our proposed plug-in rejectors is that they are only as good as the estimators we use for the density ratio $\frac{\Pr_{\rm in}(x)}{\Pr_{\rm out}(x)}$. When our estimates of the density ratio are not accurate, the plug-in rejectors are seen to often perform worse than the SIRC baseline that use the same estimates. Exploring better ways  for estimating the density ratio is an important direction for future work.

Beyond SCOD, the proposed rejection strategies are also applicable to the growing literature on adaptive inference <cit.>.  With the wide adoption of large-scale machine learning models with billions of parameters,  it is becoming increasingly important that we are able to perform speed up the inference time for these models. To this end, adaptive inference strategies have gained popularity, wherein one varies the amount of compute the model spends on an example, by for example, exiting early on “easy” examples.

The proposed approaches for SCOD may be adapted to equip early-exit models to not only exit early on high-confidence “easy” samples, but also exit early on samples that are deemed to be outliers. In the future, it would be interesting to explore the design of such early-exit models that are equipped with an OOD detector to aid in their routing decisions.