# Open-Set Likelihood Maximization for Few-Shot Learning

Malik Boudiaf ∗
ÉTS Montreal
Etienne Bennequin
CentraleSupelec
Université Paris-Saclay
Sicara Equal contribution. Corresponding authors<EMAIL_ADDRESS><EMAIL_ADDRESS>Myriam Tami
CentraleSupélec
Université Paris-Saclay  Antoine Toubhans
Sicara  Pablo Piantanida
CentraleSupélec - U. Paris-Saclay
ILLS - MILA - McGill - CNRS - ÉTS
Celine Hudelot
CentraleSupélec
Université Paris-Saclay  Ismail Ben Ayed
ÉTS Montreal

###### Abstract

We tackle the Few-Shot Open-Set Recognition (FSOSR) problem, _i.e_.
classifying instances among a set of classes for which we only have a few
labeled samples, while simultaneously detecting instances that do not belong
to any known class. We explore the popular transductive setting, which
leverages the unlabelled query instances at inference. Motivated by the
observation that existing transductive methods perform poorly in open-set
scenarios, we propose a generalization of the maximum likelihood principle, in
which latent scores down-weighing the influence of potential outliers are
introduced alongside the usual parametric model. Our formulation embeds
supervision constraints from the support set and additional penalties
discouraging overconfident predictions on the query set. We proceed with a
block-coordinate descent, with the latent scores and parametric model co-
optimized alternately, thereby benefiting from each other. We call our
resulting formulation Open-Set Likelihood Optimization (OSLO). OSLO is
interpretable and fully modular; it can be applied on top of any pre-trained
model seamlessly. Through extensive experiments, we show that our method
surpasses existing inductive and transductive methods on both aspects of open-
set recognition, namely inlier classification and outlier detection. Code is
available as part of the supplementary material.

##  1 Introduction

Few-shot classification consists in recognizing concepts for which we have
only a handful of labeled examples. These form the support set, which,
together with a batch of unlabeled instances (the query set), constitute a
few-shot task. Most few-shot methods classify the unlabeled query samples of a
given task based on their similarity to the support instances in some feature
space [34]. This implicitly assumes a closed-set setting for each task, i.e.
query instances are supposed to be constrained to the set of classes
explicitly defined by the support set. However, the real world is open and
this closed-set assumption may not hold in practice, especially for limited
support sets. Whether they are unexpected items circulating on an assembly
line, a new dress not yet included in a marketplace’s catalog, or a previously
undiscovered species of fungi, open-set instances occur everywhere. When they
do, a closed-set classifier will falsely label them as the closest known
class.

This drove the research community toward open-set recognition _i.e_.
recognizing instances with the awareness that they may belong to unknown
classes. In the large-scale settings, the literature abounds of methods
designed specifically to detect open-set instances while maintaining good
accuracy on closed-set instances [30, 1, 49]. Very recently, the authors of
[21] introduced a Few-Shot Open-Set Recognition (FSOSR) setting, in which
query instances may not belong to any known class. The study in [21], together
with other recent follow-up works [16, 15], exposed FSOSR to be a difficult
task in the inductive setting.

On the other hand, owing to its staggering performance in settings where data
is scarce [36], the transductive setting has become a prominent research
direction for few-shot classification and the subject of a large body of
recent few-shot works, e.g. [38, 9, 23, 50, 4, 41, 14, 3], among many others.
Indeed, transductive few-shot methods make joint predictions for the query
samples of each given few-shot task, rather than one sample at a time as in
the inductive setting [34]. By leveraging the statistics of the query set,
transductive methods yield performances that are substantially better than
their inductive counterparts [4, 38]. Yet we observe that current transductive
few-shot methods are significantly worse than simple inductive baselines at
detecting outliers. This might explain why transduction, despite its
popularity in few-shot learning, had not yet been explored in the FSOSR
context. Indeed, the presence of outliers in the unlabelled data tends to
conflict with existing transductive principles. Specifically, we show in our
experiments that transductive methods tend to match the classification
confidence for open-set instances with that of closed-set instances, making
prediction-based detection more difficult.

Contributions. In this work, we aim at designing a principled framework that
reconciles transduction with the open nature of the FSOSR problem. Our idea is
simple but powerful: instead of finding heuristics to assess the outlierness
of each unlabelled query sample, we treat this score as a latent variable of
the problem. Based on this idea, we propose a generalization of the maximum
likelihood principle, in which the introduced latent scores weigh potential
outliers down, thereby preventing the parametric model from fitting those
samples. Our generalization embeds additional supervision constraints from the
support set and penalties discouraging overconfident predictions. We proceed
with a block-coordinate descent optimization of our objective, with the
closed-set soft assignments, outlierness scores, and parametric models co-
optimized alternately, thereby benefiting from each other. We call our
resulting formulation Open-Set Likelihood Optimization (OSLO). OSLO provides
highly interpretable and closed-form solutions within each iteration for both
the soft assignments, outlierness variables, and the parametric model.
Additionally, OSLO is fully modular; it can be applied on top of any pre-
trained model seamlessly.

Empirically, we show that OSLO significantly surpasses its inductive and
transductive competitors alike for both outlier detection and closed-set
prediction. Applied on a wide variety of architectures and training strategies
and without any re-optimization of its parameters, OSLO’s improvement over a
strong baseline remains large and consistent. This modularity allows our
method to fully benefit from the latest advances in standard image
recognition. Before diving into the core content, let us summarize our
contributions:

  1. 1.

To the best of our knowledge, we realize the first study and benchmarking of
transductive methods for the Few-Shot Open-Set Recognition setting. We
reproduce and benchmark five state-of-the-art transductive methods.

  2. 2.

We introduce Open-Set Likelihood Optimization (OSLO), a principled extension
of the Maximum Likelihood framework that explicitly models and handles the
presence of outliers. OSLO is interpretable and modular _i.e_. can be applied
on top of any pre-trained model seamlessly.

  3. 3.

Through extensive experiments spanning five datasets and a dozen of pre-
trained models, we show that OSLO consistently surpasses both inductive and
existing transductive methods in detecting open-set instances while competing
with the strongest transductive methods in classifying closed-set instances.

##  2 Related Works

Few-shot classification (FSC) methods. Many FSC works involve episodic
training [39], in which a neural network acting as a feature extractor is
trained on artificial tasks sampled from the training set. This replication of
the inference scenario during training is intended to make the learned
representation more robust to new classes. However, several recent works have
shown that simple fine-tuning baselines are competitive in comparison to
sophisticated episodic methods, e.g. [6, 12], motivating a new direction of
few-shot learning research towards the development of model-agnostic methods
that do not involve any specific training strategy [9].

Transductive FSC. Transductive FSC methods leverage statistics of the query
set as unlabeled data to improve performance, through model fine-tuning [9],
Laplacian regularization [50], clustering [20], mutual information
maximization [4, 38], prototype rectification [23], or optimal transport [2,
14, 18], among other transduction strategies. The idea of maximizing the
likelihood of both support and query samples under a model parameterized by
class prototypes is proposed by [45] for few-shot segmentation. However, their
method relies on the closed-set assumption. Differing from previous works, our
framework leverages an additional latent variable, the inlierness score.

Open-set recognition (OSR). OSR aims to enable classifiers to detect instances
from unknown classes [30]. Prior works address this problem in the large-scale
setting by augmenting the SoftMax activation to account for the possibility of
unseen classes [1], generating artificial outliers [11, 25], improving closed-
set accuracy [37], or using placeholders to anticipate novel classes’
distributions with adaptive decision boundaries [49]. All these methods
involve the training of deep neural networks on a specific class set.
Therefore, they are not fully fit for the few-shot setting. In this work, we
use simple yet effective adaptations of OpenMax [1] and PROSER [49] as strong
baselines for FSOSR.

Few-shot open-set recognition. In the few-shot setting, methods must detect
open-set instances while only a few closed-set instances are available. [21]
use meta-learning on pseudo-open-set tasks to train a model to maximize the
classification entropy of open-set instances. [16] use transformation
consistency to measure the divergence between a query image and the set of
class prototypes. [15] use an attention mechanism to generate a negative
prototype for outliers. These methods require the optimization of a separate
model with a specific episodic training strategy. Nonetheless, as we show in
section 5, they bring marginal improvement over simple adaptations of standard
OSR methods to the few-shot setting. In comparison, our method doesn’t require
any specific training and can be plugged into any feature extractor without
further optimization.

##  3 Few-Shot Open-Set Recognition

Model training. Let us denote the raw image space $\mathcal{X}$. As per the
standard Few-Shot setting, we assume access to a base dataset
${\mathcal{D}_{\text{base}}=\\{(\bm{x}_{i},y_{i})\\}_{i=1...|\mathcal{D}_{\text{base}}|}}$
with base classes $\mathbb{C}_{\text{base}}$, such that
$\bm{x}_{i}\in\mathcal{X}$ and $y_{i}\in\mathbb{C}_{\text{base}}$. We use
$\mathcal{D}_{\text{base}}$ to train a feature extractor $\phi_{\bm{\theta}}$.
Our method developed later in section 4, freezes $\phi_{\bm{\theta}}$ and
performs inference directly on top of the extracted features for each task.

Testing. Given a set of novel classes $\mathbb{C}_{\text{novel}}$ disjoint
from base classes _i.e_.
$\mathbb{C}_{\text{novel}}\cap\mathbb{C}_{\text{base}}=\emptyset$, a $K$-way
FSOSR task is formed by sampling a set of $K$ closed-set classes
$\mathbb{C}_{\text{CS}}\subset\mathbb{C}_{\text{novel}}$, a support set of
labeled instances
$\mathbb{S}=\\{(\bm{x}_{i},y_{i})\in\mathcal{X}\times\mathbb{C}_{\text{CS}}\\}_{i=1}^{|\mathbb{S}|}$
and a query set
$\mathbb{Q}=\\{\bm{x}_{i}\in\mathcal{X}\\}_{i=|\mathbb{S}|+1}^{|\mathbb{S}|+|\mathbb{Q}|}$.
In the standard few-shot setting, the unknown ground-truth query labels
$\\{y_{i}\\}_{i=|\mathbb{S}|+1}^{|\mathbb{S}|+|\mathbb{Q}|}$ are assumed to be
restricted to closed-set classes _i.e_. $\forall
i,~{}y_{i}\in\mathbb{C}_{\text{CS}}$. In FSOSR, however, query labels may also
belong to an additional set
$\mathbb{C}_{\text{OS}}\subset\mathbb{C}_{\text{novel}}$ of open-set classes
_i.e_.
$\forall~{}i>|\mathbb{S}|,~{}y_{i}\in\mathbb{C}_{\text{CS}}\cup\mathbb{C}_{\text{OS}}$
with $\mathbb{C}_{\text{CS}}\cap\mathbb{C}_{\text{OS}}=\emptyset$. For easy
referencing, we refer to query samples from the closed-set classes
$\mathbb{C}_{\text{CS}}$ as inliers and to query samples from open-set classes
$\mathbb{C}_{\text{OS}}$ as outliers. For each query image $\bm{x}_{i}$, the
goal of FSOSR is to simultaneously assign a closed-set prediction and an
outlierness (or equivalently inlierness) score.

Transductive FSOSR. As a growing part of the Few-Shot literature, Transductive
Few-Shot Learning assumes that unlabelled samples from the query set are
observed at once, such that the structure of unlabelled data can be leveraged
to help constrain ambiguous few-shot tasks. Transductive methods have achieved
impressive improvements over inductive methods in standard closed-set FSC [9,
4, 50, 14]. We expect that transductive methods can help us improve overall
open-set performance. While we find this to generally hold for closed-set
predictive performance, we empirically show in section 5 that accuracy gains
systematically come along significant outlier detection degradation,
indicating that transductive methods are not equipped to handle open-set
recognition. In the following, we take up the challenge of designing a
transductive optimization framework that leverages the presence of outliers to
improve its performance.

##  4 Open-Set Likelihood

Figure 1: Intuition behind OSLO. Standard transductive likelihood (left) tries
to enforce high likelihood for all points, including outliers. OSLO (right)
instead treats the outlierness of each sample as a latent variable to be
solved alongside the parametric model. Besides yielding a principled
outlierness score for open-set detection, it also allows the fitted parametric
model to effectively disregard samples deemed outliers, and therefore provide
a better approximation of underlying class-conditional distributions.

In this section, we introduce OSLO, a novel extension of the standard
likelihood designed for transductive FSOSR. Unlike existing transductive
methods, OLSO explicitly models and handles the potential presence of
outliers, which allows it to outperform inductive baselines on both aspects of
the open-set scenario.

Observed variables. We start by establishing the observed variables of the
problem. As per the traditional setting, we observe images from the support
set ${\\{\bm{x}_{i}\\}_{i=1}^{|\mathbb{S}|}}$ and their associated labels
$\\{y_{i}\\}_{i=1}^{|\mathbb{S}|}$. The transductive setting also allows us to
observe images from the query set. For notation convenience, we concatenate
all images in $\bm{X}={\\{\bm{x}_{i}\\}_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}}$.

Latent variables. Our goal is to predict the class of each sample in the query
set $\mathbb{Q}$, as well as their inlierness, i.e. the model’s belief in a
sample being an inlier or not. This naturally leads us to consider latent
class assignments $\bm{z}_{i}\in\Delta^{K}$ describing the membership of
sample $i$ to each closed-set class, with
$\Delta^{K}=\\{\bm{z}\in[0,1]^{K}:\bm{z}^{T}\mathbf{1}=1\\}$ the
$K$-dimensional simplex. Additionally, we consider latent inlierness scores
$\xi_{i}\in[0,1]$ close to 1 if the model considers sample $i$ as an inlier.
For notation convenience, we consider latent assignments and inlierness scores
for all samples, including those from the support, and group everything in
$\bm{Z}=\\{\bm{z}_{i}\\}_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}$ and
$\bm{\xi}=\\{\xi_{i}\\}_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}$. Note that support
samples are inliers, and we know their class. Therefore $\forall
i\leq|\mathbb{S}|$, the constraints $\bm{z}_{i}=\bm{y}_{i}$ and $\xi_{i}=1$
will be imposed, where $\bm{y}_{i}$ is the one-hot encoded version of $y_{i}$

Parametric model. The final ingredient we need to formulate is a parametric
joint model over observed features and assignments. Following standard
practice, we model the joint distribution as a balanced mixture of standard
Gaussian distributions, parameterized by the centroids
$\bm{\mu}=\\{\bm{\mu}_{1},\dots,\bm{\mu}_{K}\\}$:

$\displaystyle
p(\bm{x},k;\bm{\mu})=p(k)p(\bm{x}|k)\propto\exp(-\frac{1}{2}\left\lVert\phi_{\bm{\theta}}(\bm{x})-\bm{\mu}_{k}\right\rVert^{2})$
(1)

As mentioned in section 3, the feature extractor’s parameters $\bm{\theta}$
are kept frozen, and only $\bm{\mu}$ will be optimized.

Objective. Using the i.i.d. assumption, we start by writing the standard
likelihood objective:

$\displaystyle
p(\bm{X},\bm{Z};\bm{\mu})=\prod_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\prod_{k=1}^{K}p(\bm{x}_{i},k;\bm{\mu})^{z_{ik}}$
(2)

Without loss of generality, we consider the log-likelihood:

$\displaystyle\log(p(\bm{X},\bm{Z};\bm{\mu}))=\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\sum_{k=1}^{K}z_{ik}\log(p(\bm{x}_{i},k;\bm{\mu}))$
(3)

Eq. (3) tries to enforce a high likelihood of all samples under our parametric
model $p$. This becomes sub-optimal in the presence of outliers, which should
ideally be disregarded. Figure 1 illustrates this phenomenon on a toy 2D
drawing. To downplay this issue, we introduce Open-Set Likelihood Optimization
(OSLO), a generalization of the standard likelihood framework, which leverages
latent inlierness scores to weigh samples:

$\displaystyle\mathcal{L}_{\text{OSLO}}(\bm{X},\bm{Z},\bm{\xi};\bm{\mu})=\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}\sum_{k=1}^{K}z_{ik}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)$
(4)

Eq (4) can be interpreted as follows: samples believed to be inliers _i.e_.
$\xi_{i}\approx 1$ will be required to have high likelihood under our model
$p$, whereas outliers won’t. Note that $\bm{\xi}$ is treated as a variable of
optimization, and is co-optimized alongside $\bm{\mu}$ and $\bm{Z}$. Finally,
to prevent overconfident latent scores, we consider a penalty term on both
$\bm{Z}$ and $\bm{\xi}$:

$\displaystyle\mathcal{L}_{\text{soft}}=\sum_{i=|\mathbb{S}|+1}^{|\mathbb{S}|+|\mathbb{Q}|}\lambda_{z}\mathcal{H}(\bm{z}_{i})+\lambda_{\xi}\mathcal{H}(\bm{\xi}_{i})$
(5)

where $\bm{\xi}_{i}=[1-\xi_{i},\xi_{i}]$, and
$\mathcal{H}(\bm{p})=-\bm{p}^{\top}\log(\bm{p})$ denotes the entropy, which
encourages smoother assignments.

Optimization. We are now ready to formulate OSLO’s optimization problem:

$\displaystyle\max_{\bm{\mu},\bm{Z},\bm{\xi}}$
$\displaystyle\quad\mathcal{L}_{\text{OSLO}}(\bm{Z},\bm{\xi},\bm{\mu})+\mathcal{L}_{\text{soft}}(\bm{Z},\bm{\xi})$
s.t
$\displaystyle\quad\bm{z}_{i}\in\Delta^{K},\quad\xi_{i}\in[0,1]\quad\forall~{}i$
(6) $\displaystyle\quad\bm{z}_{i}=\bm{y}_{i},\quad\xi_{i}=1,\quad
i\leq|\mathbb{S}|$

Problem (4) is strictly convex with respect to each variable when the other
variables are fixed. Therefore, we proceed with a block-coordinate ascent,
which alternates three iterative steps, each corresponding to a closed-form
solution for one of the variables.

######  Proposition 1.

OSLO’s optimization problem (4) can be minimized by alternating the following
updates:

$\displaystyle\xi_{i}^{(t+1)}$ $\displaystyle=\begin{cases}1\quad\text{if
}i\leq|\mathbb{S}|\\\
\sigma\left(\displaystyle\frac{1}{\lambda_{\xi}}\displaystyle\sum_{k=1}^{K}z_{ik}^{(t)}\log
p(\bm{x}_{i},k;\bm{\mu}^{(t)}))\right)\text{else}\end{cases}$
$\displaystyle\bm{z}_{i}^{(t+1)}$
$\displaystyle\propto\begin{cases}\bm{y}_{i}\quad\text{if
}i\leq|\mathbb{S}|\\\
\exp\left(\displaystyle\frac{\xi_{i}^{(t+1)}}{\lambda_{z}}\log
p(\bm{x}_{i},~{}\cdot~{};\bm{\mu}^{(t)})\right)\text{else}\end{cases}$
$\displaystyle\bm{\mu}^{(t+1)}_{k}$
$\displaystyle=\frac{1}{\displaystyle\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}^{(t+1)}z_{ik}^{(t+1)}}\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}^{(t+1)}z_{ik}^{(t+1)}\phi_{\theta}(\bm{x}_{i})$

where $\sigma$ denotes the sigmoid operation.

The proof of proposition 1 is performed by derivation of
$\mathcal{L}_{\text{OSLO}}(\bm{Z},\bm{\xi},\bm{\mu})+\mathcal{L}_{\text{soft}}(\bm{Z},\bm{\xi})$
and deferred to the supplementary material. The optimal solution for the
inlierness score $\xi_{i}$ appears very intuitive, and essentially conveys
that samples with high likelihood under the current parametric model should be
considered inliers. We emphasize that beyond providing a principled
outlierness score, as $1-\xi_{i}$, the presence of $\xi_{i}$ allows to refine
and improve the closed-set parametric model. In particular, $\xi_{i}$ acts as
a sample-wise temperature in the update of $\bm{z}_{i}$, encouraging outliers
($\xi_{i}\approx 0$) to have a uniform distribution over closed-set classes.
Additionally, those samples contribute less to the update of closed-set
prototypes $\bm{\mu}$, as each sample’s contribution is weighted by $\xi_{i}$.

##  5 Experiments

###  5.1 Experimental setup

Table 1: Standard Benchmarking. Evaluating different families of methods on
the FSOSR problem on mini-ImageNet and tiered-ImageNet using a ResNet-12. For
each column, a light-gray standard deviation is indicated, corresponding to
the maximum deviation observed across methods for that metric. Best methods
are shown in bold. Results marked with ⋆ are reported from their original
paper.

|  |  mini-ImageNet
---|---|---
Strategy | Method | 1-shot | 5-shot
Acc | AUROC | AUPR |<EMAIL_ADDRESS>| Acc | AUROC | AUPR |<EMAIL_ADDRESS>
$\pm{0.72}$ | $\pm{0.79}$ | $\pm{0.69}$ | $\pm{0.47}$ | $\pm{0.44}$ | $\pm{0.73}$ | $\pm{0.61}$ | $\pm{0.56}$
OOD detection |  $k$-NN[26] | - | 70.86 | 70.43 | 58.23 | - | 76.22 | 76.36 | 61.48
IForest [22] | - | 55.59 | 55.24 | 52.18 | - | 62.80 | 61.62 | 54.77
OCVSM [31] | - | 69.67 | 69.71 | 57.35 | - | 68.49 | 65.60 | 59.24
PCA [33] | - | 67.23 | 66.50 | 56.67 | - | 75.24 | 75.53 | 60.73
COPOD [19] | - | 50.60 | 51.85 | 50.92 | - | 51.63 | 52.65 | 51.31
HBOS | - | 58.26 | 57.41 | 53.06 | - | 61.11 | 60.18 | 54.30
Inductive classifiers |  SimpleShot [40] | 65.90 | 64.99 | 63.78 | 55.77 | 81.72 | 70.61 | 70.06 | 57.91
Baseline ++ [6] | 65.81 | 65.15 | 63.85 | 55.87 | 81.86 | 66.37 | 65.58 | 56.33
FEAT [46] | 67.23 | 52.45 | 54.44 | 50.00 | 82.00 | 53.25 | 56.48 | 50.00
Inductive Open-Set |  PEELER⋆ [21] | 65.86 | 60.57 | - | - | 80.61 | 67.35 | - | -
TANE-G⋆ [15] | 68.11 | 72.41 | - | - | 83.12 | 79.85 | - | -
SnatcherF [16] | 67.23 | 70.10 | 69.74 | 58.02 | 82.00 | 76.57 | 76.97 | 61.64
OpenMax [1] | 65.90 | 71.34 | 70.86 | 58.67 | 82.23 | 77.42 | 77.63 | 62.35
|  PROSER [49] | 65.00 | 68.93 | 68.84 | 57.03 | 80.08 | 74.98 | 75.58 | 60.11
Transductive classifiers |  LaplacianShot [50] | 70.59 | 53.13 | 54.59 | 52.06 | 82.94 | 57.17 | 57.90 | 52.56
BDCSPN [23] | 69.35 | 57.95 | 58.58 | 52.71 | 82.66 | 61.27 | 62.17 | 53.26
TIM-GD [4] | 67.53 | 62.46 | 61.05 | 54.83 | 82.49 | 67.19 | 66.15 | 56.70
PT-MAP [14] | 66.32 | 59.05 | 58.67 | 53.74 | 78.12 | 62.78 | 62.48 | 54.67
LR-ICI [41] | 68.24 | 49.96 | 51.61 | 50.45 | 81.77 | 51.82 | 53.49 | 50.80
Transductive Open-Set | OSLO (ours) | 71.73 | 74.92 | 74.61 | 60.95 | 83.40 | 82.59 | 82.34 | 66.98
|  |  tiered-ImageNet
|  | $\pm{0.74}$ | $\pm{0.76}$ | $\pm{0.71}$ | $\pm{0.52}$ | $\pm{0.52}$ | $\pm{0.68}$ | $\pm{0.75}$ | $\pm{0.57}$
OOD detection |  $k$-NN[26] | - | 73.97 | 73.15 | 60.74 | - | 80.22 | 80.06 | 65.47
IForest [22] | - | 54.57 | 54.24 | 51.85 | - | 62.31 | 60.82 | 54.72
OCVSM [31] | - | 71.22 | 71.17 | 58.81 | - | 71.20 | 68.23 | 61.09
PCA [33] | - | 68.30 | 67.02 | 57.66 | - | 76.26 | 76.41 | 61.81
COPOD [19] | - | 50.87 | 51.95 | 51.07 | - | 52.62 | 53.48 | 51.44
HBOS | - | 57.54 | 56.67 | 52.98 | - | 60.91 | 59.95 | 54.15
Inductive classifiers |  SimpleShot [40] | 70.27 | 69.78 | 67.89 | 58.54 | 84.94 | 77.38 | 76.28 | 63.21
Baseline ++ [6] | 70.21 | 69.73 | 67.80 | 58.50 | 85.10 | 73.77 | 72.39 | 61.05
FEAT [46] | 69.94 | 52.49 | 56.74 | 50.00 | 83.96 | 53.30 | 59.81 | 50.00
Inductive Open-Set |  PEELER⋆ [21] | 69.51 | 65.20 | - | - | 84.10 | 73.27 | - | -
TANE-G⋆ [15] | 70.58 | 73.53 | - | - | 85.38 | 81.54 | - | -
SnatcherF [16] | 69.94 | 74.02 | 73.33 | 60.79 | 83.96 | 81.90 | 81.67 | 66.89
OpenMax [1] | 70.27 | 72.40 | 71.91 | 59.91 | 85.79 | 77.91 | 78.42 | 63.07
|  PROSER [49] | 68.48 | 70.07 | 69.87 | 57.99 | 83.34 | 75.84 | 76.56 | 61.12
Transductive classifiers |  LaplacianShot [50] | 75.66 | 57.82 | 58.41 | 53.67 | 86.23 | 63.75 | 63.65 | 55.36
BDCSPN [23] | 74.07 | 62.13 | 61.84 | 54.53 | 85.65 | 67.41 | 67.57 | 56.30
TIM-GD [4] | 72.56 | 68.08 | 65.97 | 57.84 | 85.70 | 74.67 | 73.06 | 61.59
PT-MAP [14] | 71.13 | 64.48 | 62.94 | 56.25 | 82.81 | 71.08 | 69.89 | 59.11
LR-ICI [41] | 73.80 | 49.32 | 51.41 | 50.35 | 85.21 | 51.65 | 53.85 | 50.79
Transductive Open-Set | OSLO (ours) | 76.64 | 79.06 | 79.07 | 64.36 | 86.35 | 86.92 | 87.28 | 71.98

Figure 2: OSLO improves open-set performances on a wide variety of tasks.
Relative 1-shot performance of the best methods of each family w.r.t the
Strong baseline using a ResNet-12, across a set of 5 scenarios, including 3
with domain-shift. Each vertex represents one scenario, e.g.
tiered$\rightarrow$Fungi ($x$) means the feature extractor was pre-trained on
tiered-ImageNet, test tasks are sampled from Fungi, and the Strong Baseline
performance is $x$. For each method, the average relative improvement across
the 5 scenarios is reported in parenthesis in the legend. The same charts are
provided in the supplementary materials for the 5shot setting and using a
WideResNet backbone.

Baselines. One goal of this work is to fairly evaluate different strategies to
address the FSOSR problem. In particular, we benchmark 4 families of methods:
(i) popular Outlier Detection methods, e.g. Nearest-Neighbor [26], (ii)
Inductive Few-Shot classifiers, e.g. SimpleShot [40] (iii) Inductive Open-Set
methods formed by standard methods such as OpenMax [1] and Few-Shot methods
such as Snatcher [16] (iv) Transductive classifiers, e.g. TIM [4], that
implicitly rely on the closed-set assumption, and finally (v) Transductive
Open-Set introduced in this work through OSLO. Following [16], closed-set few-
shot classifiers are turned into open-set classifiers by considering the
negative of the maximum probability as a measure of outlierness. Furthermore,
we found that applying a center-normalize transformation
$\psi_{\bm{\upsilon}}:\bm{x}\mapsto(\bm{x}-\bm{\upsilon})/||\bm{x}-\bm{\upsilon}||_{2}$
on the features extracted by $\phi_{\bm{\theta}}$ benefited all methods.
Therefore, we apply it to the features before applying any method, using an
inductive Base centering [40] for inductive methods
$\bm{\upsilon}_{Base}=\frac{1}{|\mathcal{D}_{base}|}\sum_{\bm{x}\in\mathcal{D}_{base}}\phi_{\bm{\theta}}(x)$,
and a transductive Task centering [14]
${\bm{\upsilon}_{Task}=\frac{1}{|\mathbb{S}\cup\mathbb{Q}|}\sum_{\bm{x}\in\mathbb{S}\cup\mathbb{Q}}\phi_{\bm{\theta}}(x)}$
for all transductive methods. Since features are normalized, we empirically
found it beneficial to re-normalize centroids
$\bm{\mu}_{k}\leftarrow\bm{\mu}_{k}/||\bm{\mu}_{k}||_{2}$ after each update
from Prop. 1, which we show in the Appendix remains a valid minimizer of Sec.
4 when adding the constraint $||\bm{\mu}_{k}||_{2}=1$.

Hyperparameters. For all methods, we define a grid over salient hyper-
parameters and tune over the validation split of mini-ImageNet. To avoid
cumbersome per-dataset tuning, and evaluate the generalizability of methods,
we then keep hyper-parameters fixed across all other experiments.

Architectures and checkpoints. To provide the fairest comparison, all non-
episodic methods are tuned and tested using off-the-shelf pre-trained
checkpoints. All results except Figure 4 are produced using the pre-trained
ResNet-12 and Wide-ResNet 28-10 checkpoints provided by the authors from [46].
As for episodically-finetuned models required by Snatcher [16] and FEAT [46],
checkpoints are obtained from the authors’ respective repositories. Finally,
to challenge the model-agnosticity of our method, we resort to an additional
set of 10 ImageNet pre-trained models covering three distinct architectures:
ResNet-50 [13] for CNNs, ViT-B/16 [10] for vision transformers, and Mixer-B/16
[35] for MLP-Mixer. Most models used are taken from the excellent TIMM library
[43].

Datasets and tasks. We experiment with a total of 5 vision datasets. As
standard FSC benchmarks, we use the mini-ImageNet [39] dataset with 100
classes and the larger tiered-ImageNet [27] dataset with 608 classes. We also
experiment on more challenging cross-domain tasks formed by using 3 finer-
grained datasets: the Caltech-UCSD Birds 200 [42] (CUB) dataset, with 200
classes, the FGVC-Aircraft dataset [24] with 100 classes, and the Fungi
classification challenge [32] with 1394 classes. Following standard FSOSR
protocol, support sets contain $|\mathbb{C}_{\text{CS}}|=5$ closed-set classes
with 1 or 5 instances, or shots, per class, and query sets are formed by
sampling 15 instances per class, from a total of ten classes: the five closed-
set classes and an additional set of $|\mathbb{C}_{\text{OS}}|=5$ open-set
classes. We follow this setting for a fair comparison with previous works [16,
21] which sample open-set query instances from only 5 classes. We also report
results in supplementary materials for a more general setting in which open-
set query instances are sampled indifferently from all remaining classes in
the test set.

###  5.2 Results

Simplest inductive methods are competitive. The first surprising result comes
from analyzing the performances of standard OOD detectors on the FSOSR
problem. Table 1 shows that $k$-NN and PCA outperform, by far, arguably more
advanced methods that are OCVSM and Isolation Forest. This result contrasts
with standard high-dimensional benchmarks [48] where $k$-NN falls typically
short of the latter, indicating that the very difficult challenge posed by
FSOSR may lead advanced methods to overfit. In fact, Figure 2 shows that
across 5 scenarios, the combination SimpleShot [40]\+ $k$-NN [26] formed by
the simplest FS-inductive classifier and the simplest inductive OOD detector
is a strong baseline that outperforms all specialized open-set methods. We
refer to this combination as Strong baseline in Figures 2 and 4. Additional
results for the Wide-ResNet architecture are provided in the supplementary
material.

Figure 3: OSLO improves performance even with few queries. We study the
closed-set (accuracy) and open-set (AUROC) performance of transductive methods
depending on the size of the query set on tiered-ImageNet in the 1-shot and
5-shot settings. The total size $|Q|$ of the query set is obtained by
multiplying the number of queries per class $N_{Q}$ by the number of classes
in the task (_i.e_. 5) and adding as many outlier queries _e.g_. $N_{Q}=1$
corresponds to 1 query per class and 5 open-set queries _i.e_. $|Q|=10$. We
add the inductive method $k$-NN + SimpleShot to compare with a method that is
by nature independent of the number of queries. The results for mini-ImageNet
are provided in the supplementary materials.

Transductive methods still improve accuracy but degrade outlier detection. As
shown in Table 1, most transductive classifiers still offer a significant
boost in closed-set accuracy, even in the presence of outliers in the query
set. Note that this contrasts with findings from the semi-supervised
literature, where standard methods drop below the baseline in the presence of
even a small fraction of outliers [47, 8, 29, 17]. We hypothesize that the
deliberate under-parametrization of few-shot methods –typically only training
a linear classifier–, required to avoid overfitting the support set, partly
explains such robustness. However, transductive methods still largely
underperform in outlier detection, with AUROCs as low as 52 % (50% being a
random detector) for LaplacianShot. Note that the outlierness score for these
methods is based on the negative of the maximum probability, therefore this
result can be interpreted as transductive methods having artificially matched
the prediction confidence for outliers with the confidence for inliers.

OSLO achieves the best trade-off. Benchmark results in Table 1 show that OSLO
surpasses the best transductive methods in terms of closed-set accuracy, while
consistently outperforming existing out-of-distribution and open-set detection
competitors on outlier detection ability. Interestingly, while the gap between
closed-set accuracy of transductive methods and inductive ones typically
contracts with more shots, the outlier detection performance of OSLO remains
largely superior to its inductive competitors even in the 5-shot scenario,
where a consistent 3-6% gap in AUROC and AUPR with the second-best method can
be observed. We accumulate further evidence of OSLO’s superiority by
introducing 3 additional cross-domain scenarios in Figure 2, corresponding to
a base model pre-trained on tiered-ImageNet, but tested on CUB, Aircraft, and
Fungi datasets. In such challenging scenarios, where both feature and class
distributions shift, OSLO remains competitive in closed-set accuracy and
largely outperforms other methods in outlier detection.

OSLO benefits from more query samples. A critical question for transductive
methods is the dependency of their performance on the size of the query set.
Intuitively, a larger query set will provide more unlabeled data and thus lead
to better results. We exhibit this relation in Figure 3 by spanning the number
of queries per class from 1 to 30. We observe that the closed-set accuracy of
most transductive methods is stable across this span in the 5-shot scenario.
In the 1-shot scenario, OSLO gains from additional queries but stays above the
baseline even with a small number of queries. Interestingly enough, OSLO is
the only transductive method to improve its outlier detection ability when the
number of queries increases.

Figure 4: OSLO’s improvement is consistent across many architectures and
training strategies. To evaluate model-agnosticity, we compare OSLO to the
Strong baseline on challenging 1-shot Fungi tasks. We experiment across 3
largely distinct architectures: ResNet-50 (CNN) [13], ViT-B/16 (Vision
Transformer) [10], and Mixer-B/16 (MLP-Mixer) [35]. For each architecture, we
include different types of pre-training, including Supervised (Sup.), Semi-
Supervised, Semi-Weakly Supervised (SW Sup.) [44], DINO [5], SAM [7], MIIL
[28]. Improvements over the baseline are consistently significant and
generally higher than those observed with the ResNet-12 in Figure 2. Table 2:
OSLO’s ablation study along two factors described in Table 2. Results are
produced on the 1-shot scenario on mini-ImageNet, with a ResNet-12.

(i) Inlierness latent | Acc | AUROC
---|---|---
Ignore (3) | 69.42 | 64.97
Leverage (4) | 71.73 | 74.92
(ii) Optimization steps | Acc | AUROC
At initialization | 66.63 | 71.76
After optimization | 71.73 | 74.92

OSLO steps toward model-agnosticity. We evaluate OSLO’s model-agnosticity by
its ability to maintain consistent improvement over the Strong Baseline,
regardless of the model used, and without hyperparameter adjustment. In that
regard, we depart from the standard ResNet-12 and cover 3 largely distinct
architectures, each encoding different inductive biases. To further strengthen
our empirical demonstration of OSLO’s model-agnosticity, for each
architecture, we consider several training strategies spanning different
paradigms – unsupervised, supervised, semi and semi-weakly supervised – and
using different types of data –image, text–. Results in Figure 4 show the
relative improvement of OSLO w.r.t the strong baseline in the 1-shot scenario
on the $\ast\rightarrow$ Fungi benchmark. Without any tuning, OSLO remains
able to leverage the strong expressive power of large-scale models, and even
consistently widens the gap with the strong baseline, achieving a remarkable
performance of 79% accuracy and 81% AUROC with the ViT-B/16. This set of
results testifies to how easy obtaining highly competitive results on
difficult specialized tasks can be by combining OSLO with the latest models.

Ablation study. We perform an ablation study on the important ingredients of
OSLO. As a core contribution of our work, we show in Tab. 2 that the presence
_and_ optimization of the latent inlierness scores is crucial. In particular,
the closed-form latent score $\xi$ yields strong outlier recognition
performance, even at initialization (i.e. after the very first update from
Prop. 1). Interestingly, refining the parametric model without accounting for
$\bm{\xi}$ in $\mathbf{Z}$ and $\bm{\mu}$’s updates (i.e. standard likelihood)
allows the model to fit those outliers, leading to significantly worse outlier
detection, from $71.76\%$ to $64.97\%$. On the other hand, accounting for
$\bm{\xi}$, as proposed in OSLO, improves the outlier detection by more than
$3\%$ over the initial state, and closed-set accuracy by more than $5\%$. In
the end, in a fully apples-to-apples comparison, OSLO outperforms its standard
likelihood counterpart by more than $2\%$ in accuracy and $10\%$ in outlier
detection.

##  6 Discussion

Limitations. Unlike inductive methods, transductive methods are inevitably
affected by the amount of unlabelled data provided, which in real-world
scenarios cannot necessarily be controlled. OSLO is no exception, and fewer
query samples tend to decrease its performance. In the extreme case with only
1 sample per class, OSLO’s performance comes close to our inductive baseline.
In those scenarios where unlabelled data is particularly scarce, the benefits
brought by transduction remain therefore limited. As a second limitation,
poorer representations appear to diminish OSLO’s competitive advantage in
closed-set accuracy. In particular, OSLO’s closed-set accuracy stands more
than $6\%$ above the baseline in the in-domain
$\textit{tiered}\rightarrow\textit{tiered}$ scenario but reduces to $2\%$ in
the most challenging-domain scenario
$\textit{tiered}\rightarrow\textit{Aircraft}$. Fig. 4 further corroborates
this hypothesis, with OSLO’s accuracy outperforming the baseline’s by $9\%$
with the best transformer, but by only $2.7\%$ on the least performing model.

Conclusion. We presented OSLO, the first transductive method for FSOSR. OSLO
extends the vanilla maximum likelihood objective in two important ways, First,
it accounts for the constraints imposed by the provided supervision. More
importantly, it explicitly models the potential presence of outliers in its
very latent model, allowing it to co-learn the optimal closed-set model and
outlier assignments. Beyond FSOSR, we believe OSLO presents a general,
conceptually simple, and completely modular formulation to leverage unlabelled
data in the potential presence of outliers. That, of course, naturally extends
to other classification settings, such as large-scale open-set detection, but
to other tasks as well, such as segmentation in which background pixels could
be viewed as outliers with respect to closed-set classes. We hope OSLO
inspires further work in that direction.

## References

  * [1] Abhijit Bendale and Terrance E Boult.  Towards open set deep networks.  In Computer Vision and Pattern Recognition Conference (CVPR), 2016\.
  * [2] Etienne Bennequin, Victor Bouvier, Myriam Tami, Antoine Toubhans, and Céline Hudelot.  Bridging few-shot learning and adaptation: New challenges of support-query shift.  European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2021.
  * [3] Malik Boudiaf, Hoel Kervadec, Ziko Imtiaz Masud, Pablo Piantanida, Ismail Ben Ayed, and Jose Dolz.  Few-shot segmentation without meta-learning: A good transductive inference is all you need?  In Computer Vision and Pattern Recognition Conference (CVPR), 2021\.
  * [4] Malik Boudiaf, Ziko Imtiaz Masud, Jérôme Rony, José Dolz, Pablo Piantanida, and Ismail Ben Ayed.  Transductive information maximization for few-shot learning.  In Neural Information Processing Systems (NeurIPS), 2020.
  * [5] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In ICCV, 2021.
  * [6] Wei-Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Wang, and Jia-Bin Huang.  A closer look at few-shot classification.  In International Conference on Learning Representations (ICLR), 2019\.
  * [7] Xiangning Chen, Cho-Jui Hsieh, and Boqing Gong.  When vision transformers outperform resnets without pre-training or strong data augmentations.  International Conference on Learning Representations (ICLR), 2022\.
  * [8] Yanbei Chen, Xiatian Zhu, Wei Li, and Shaogang Gong.  Semi-supervised learning under class distribution mismatch.  In Conference on Artificial Intelligence (AAAI), 2020.
  * [9] Guneet Singh Dhillon, Pratik Chaudhari, Avinash Ravichandran, and Stefano Soatto.  A baseline for few-shot image classification.  In International Conference on Learning Representations (ICLR), 2020\.
  * [10] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  International Conference on Learning Representations (ICLR), 2021\.
  * [11] ZongYuan Ge, Sergey Demyanov, Zetao Chen, and Rahil Garnavi.  Generative openmax for multi-class open set classification.  arXiv, 2017.
  * [12] Micah Goldblum, Steven Reich, Liam Fowl, Renkun Ni, Valeriia Cherepanova, and Tom Goldstein.  Unraveling meta-learning: Understanding feature representations for few-shot tasks.  In International Conference on Machine Learning (ICML), 2020.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Computer Vision and Pattern Recognition Conference (CVPR), 2016\.
  * [14] Yuqing Hu, Vincent Gripon, and Stéphane Pateux.  Leveraging the feature distribution in transfer-based few-shot learning.  In International Conference on Artificial Neural Networks, 2021\.
  * [15] Shiyuan Huang, Jiawei Ma, Guangxing Han, and Shih-Fu Chang.  Task-adaptive negative envision for few-shot open-set recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7171–7180, 2022.
  * [16] Minki Jeong, Seokeon Choi, and Changick Kim.  Few-shot open-set recognition by transformation consistency.  In Computer Vision and Pattern Recognition Conference (CVPR), 2021\.
  * [17] Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer.  Retrieve: Coreset selection for efficient and robust semi-supervised learning.  Neural Information Processing Systems (NeurIPS), 34, 2021.
  * [18] Michalis Lazarou, Tania Stathaki, and Yannis Avrithis.  Iterative label cleaning for transductive and semi-supervised few-shot learning.  In ICCV, 2021.
  * [19] Zheng Li, Yue Zhao, Nicola Botta, Cezar Ionescu, and Xiyang Hu.  Copod: copula-based outlier detection.  In International Conference on Data Mining (ICDM), 2020.
  * [20] Moshe Lichtenstein, Prasanna Sattigeri, Rogerio Feris, Raja Giryes, and Leonid Karlinsky.  Tafssl: Task-adaptive feature sub-space learning for few-shot classification.  In European Conference on Computer Vision (ECCV), 2020.
  * [21] Bo Liu, Hao Kang, Haoxiang Li, Gang Hua, and Nuno Vasconcelos.  Few-shot open-set recognition using meta-learning.  In Computer Vision and Pattern Recognition Conference (CVPR), 2020\.
  * [22] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou.  Isolation forest.  In International Conference on Data Mining (ICMD), 2008.
  * [23] Jinlu Liu, Liang Song, and Yongqiang Qin.  Prototype rectification for few-shot learning.  In European Conference on Computer Vision (ECCV), 2020.
  * [24] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi.  Fine-grained visual classification of aircraft.  arXiv, 2013.
  * [25] Lawrence Neal, Matthew Olson, Xiaoli Fern, Weng-Keen Wong, and Fuxin Li.  Open set learning with counterfactual images.  In European Conference on Computer Vision (ECCV), 2018.
  * [26] Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim.  Efficient algorithms for mining outliers from large data sets.  In International Conference on Management of Data, 2000.
  * [27] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenenbaum, Hugo Larochelle, and Richard S Zemel.  Meta-learning for semi-supervised few-shot classification.  International Conference on Learning Representations (ICLR), 2018\.
  * [28] Tal Ridnik, Emanuel Ben-Baruch, Asaf Noy, and Lihi Zelnik-Manor.  Imagenet-21k pretraining for the masses.  Neural Information Processing Systems (NeurIPS), 2021.
  * [29] Kuniaki Saito, Donghyun Kim, and Kate Saenko.  Openmatch: Open-set semi-supervised learning with open-set consistency regularization.  Neural Information Processing Systems (NeurIPS), 2021.
  * [30] Walter J Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult.  Toward open set recognition.  PAMI, 2012.
  * [31] Bernhard Schölkopf, John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson.  Estimating the support of a high-dimensional distribution.  Neural computation, 2001.
  * [32] Brigit Schroeder and Yin Cui.  Fgvcx fungi classification challenge 2018.  2018\.
  * [33] Mei-Ling Shyu, Shu-Ching Chen, Kanoksri Sarinnapakorn, and LiWu Chang.  A novel anomaly detection scheme based on principal component classifier.  Technical report, 2003.
  * [34] Jake Snell, Kevin Swersky, and Richard S Zemel.  Prototypical networks for few-shot learning.  Neural Information Processing Systems (NeurIPS), 2017.
  * [35] Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al.  Mlp-mixer: An all-mlp architecture for vision.  Neural Information Processing Systems (NeurIPS), 2021.
  * [36] Vladimir Vapnik.  The nature of statistical learning theory.  Springer science & business media, 2013.
  * [37] Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman.  Open-set recognition: A good closed-set classifier is all you need.  In International Conference on Learning Representations (ICLR), 2022\.
  * [38] Olivier Veilleux, Malik Boudiaf, Pablo Piantanida, and Ismail Ben Ayed.  Realistic evaluation of transductive few-shot learning.  Neural Information Processing Systems (NeurIPS), 2021.
  * [39] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  In Neural Information Processing Systems (NeurIPS), 2016.
  * [40] Yan Wang, Wei-Lun Chao, Kilian Q Weinberger, and Laurens van der Maaten.  Simpleshot: Revisiting nearest-neighbor classification for few-shot learning.  arXiv, 2019.
  * [41] Yikai Wang, Chengming Xu, Chen Liu, Li Zhang, and Yanwei Fu.  Instance credibility inference for few-shot learning.  In Computer Vision and Pattern Recognition Conference (CVPR), 2020\.
  * [42] Peter Welinder, Steve Branson, Takeshi Mita, Catherine Wah, Florian Schroff, Serge Belongie, and Pietro Perona.  Caltech-ucsd birds 200.  2010\.
  * [43] Ross Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * [44] I Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan.  Billion-scale semi-supervised learning for image classification.  arXiv, 2019.
  * [45] Boyu Yang, Chang Liu, Bohao Li, Jianbin Jiao, and Qixiang Ye.  Prototype mixture models for few-shot semantic segmentation.  In European Conference on Computer Vision, pages 763–778. Springer, 2020.
  * [46] Han-Jia Ye, Hexiang Hu, De-Chuan Zhan, and Fei Sha.  Few-shot learning via embedding adaptation with set-to-set functions.  In Computer Vision and Pattern Recognition Conference (CVPR), 2020\.
  * [47] Qing Yu, Daiki Ikami, Go Irie, and Kiyoharu Aizawa.  Multi-task curriculum framework for open-set semi-supervised learning.  In European Conference on Computer Vision (ECCV), 2020.
  * [48] Yue Zhao, Zain Nasrullah, and Zheng Li.  Pyod: A python toolbox for scalable outlier detection.  JMLR, 2019.
  * [49] Da-Wei Zhou, Han-Jia Ye, and De-Chuan Zhan.  Learning placeholders for open-set recognition.  In Computer Vision and Pattern Recognition Conference (CVPR), 2021\.
  * [50] Imtiaz Ziko, Jose Dolz, Eric Granger, and Ismail Ben Ayed.  Laplacian regularized few-shot learning.  In International Conference on Machine Learning (ICML), 2020.

##  Appendix A Proof of Proposition 1

Reminder of Proposition 1 OSLO’s optimization problem, being defined in (4)
as:

$\displaystyle\max_{\bm{\mu},\bm{Z},\bm{\xi}}$
$\displaystyle\quad\mathcal{L}_{\text{OSLO}}(\bm{Z},\bm{\xi},\bm{\mu})+\mathcal{L}_{\text{soft}}(\bm{Z},\bm{\xi})$
s.t
$\displaystyle\quad\bm{z}_{i}\in\Delta^{K},\quad\xi_{i}\in[0,1]\quad\forall~{}i$
$\displaystyle\quad\bm{z}_{i}=\bm{y}_{i},\quad\xi_{i}=1,\quad
i\leq|\mathbb{S}|$

can be minimized by alternating the following updates:

$\displaystyle\xi_{i}^{(t+1)}$ $\displaystyle=\begin{cases}1\quad\text{if
}i\leq|\mathbb{S}|\\\
\sigma\left(\displaystyle\frac{1}{\lambda_{\xi}}\displaystyle\sum_{k=1}^{K}z_{ik}^{(t)}\log
p(\bm{x}_{i}|k;\bm{\mu}^{(t)}))\right)\text{else}\end{cases}$
$\displaystyle\bm{z}_{i}^{(t+1)}$
$\displaystyle\propto\begin{cases}\bm{y}_{i}\quad\text{if
}i\leq|\mathbb{S}|\\\
\exp\left(\displaystyle\frac{\xi_{i}^{(t+1)}}{\lambda_{z}}\log
p(\bm{x}_{i}|~{}\cdot~{};\bm{\mu}^{(t)})\right)\text{else}\end{cases}$
$\displaystyle\bm{\mu}^{(t+1)}_{k}$
$\displaystyle=\frac{1}{\displaystyle\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}^{(t+1)}z_{ik}^{(t+1)}}\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}^{(t+1)}z_{ik}^{(t+1)}\phi_{\theta}(\bm{x}_{i})$

where $\sigma$ denotes the sigmoid operation.

###### Proof.

We denote by
$\nabla_{\cdot}(\mathcal{L}_{\text{OSLO}}+\mathcal{L}_{\text{soft}})$ the
partial derivative of OSLO’s optimization problem. We calculate the updates of
$\xi_{i}$ and $z_{ik}$ for $i>|S|$, and of $\bm{\mu}_{k}$, by finding the
annulation point of their partial derivative.

$\displaystyle\nabla_{\xi_{i}}(\mathcal{L}_{\text{OSLO}}+\mathcal{L}_{\text{soft}})=0$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\sum_{k=1}^{K}z_{ik}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)$
$\displaystyle\quad=\lambda_{\xi}\left((\log\xi_{i}+1)-(\log(1-\xi_{i})+1)\right)$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\frac{1}{\lambda_{\xi}}\sum_{k=1}^{K}z_{ik}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)=\log\left(\frac{\xi_{i}}{1-\xi_{i}}\right)$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\xi_{i}=\sigma\left(\frac{1}{\lambda_{\xi}}\sum_{k=1}^{K}z_{ik}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)\right)$

$\displaystyle\nabla_{z_{ik}}(\mathcal{L}_{\text{OSLO}}+\mathcal{L}_{\text{soft}})=0$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\xi_{i}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)=\lambda_{z}\left(\log
z_{ik}+1\right)$ $\displaystyle\Rightarrow\quad$ $\displaystyle
z_{ik}\propto\exp\left(\frac{\xi_{i}}{\lambda_{z}}\log\left(p(\bm{x}_{i},k;\bm{\mu})\right)\right)$

$\displaystyle\nabla_{\bm{\mu}_{k}}(\mathcal{L}_{\text{OSLO}}+\mathcal{L}_{\text{soft}})=0$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}\left(\phi_{\bm{\theta}}(\bm{x}_{i})-\bm{\mu}_{k}\right)=0$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\bm{\mu}_{k}=\dfrac{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}\phi_{\bm{\theta}}(\bm{x}_{i})}{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}}$

∎

##  Appendix B Normalizing centroids

Because we work with normalized features, we state in our implementation
details that we found normalizing $||\bm{\mu}||$ after each update helps. Here
we show that this "projected step" is actually the exact solution to the
optimization problem Sec. 4 when adding the constraint
$\bm{\mu}\in\mathcal{B}_{2}$, where
$\mathcal{B}_{2}=\\{\bm{x}:||\bm{x}||_{2}=1\\}$ is the unit hypersphere.

Specifically, adding the constraint $\bm{\mu}\in\mathcal{B}_{2}$ modifies the
Lagrangian by infinitely penalizing $\bm{\mu}_{k}$ for being outside the unit
hypersphere. Without loss of generality, we only consider the part of the
Lagrangian pertaining to $\bm{\mu}_{k}$ for some $k\in[1,K]$, which we refer
to as $\mathcal{L}_{k}$:

$\displaystyle\mathcal{L}_{k}(\bm{\mu}_{k})=\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}||\bm{\mu}_{k}-\phi_{\theta}(\bm{x}_{i})||^{2}+\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$

where $\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$ equals 0 if
$\bm{\mu}_{k}\in\mathcal{B}_{2}$ and $\infty$ otherwise. Because
$\mathcal{L}_{k}$ is no longer differentiable, we introduce the
subdifferential operator $\partial_{\cdot}(\cdot)$, which generalizes the
standard notion of differentiability. Akin to the standard case, we look for
$\bm{\mu}_{k}$ such that:

$\displaystyle 0\in\partial_{\bm{\mu}_{k}}\mathcal{L}_{k}(\bm{\mu}_{k}),$

which amounts to:

$\displaystyle\Leftrightarrow$ $\displaystyle\quad
0\in\\{\nabla_{\bm{\mu}_{k}}\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}||\bm{\mu}_{k}-\phi_{\theta}(\bm{x}_{i})||^{2}\\}+\partial_{\bm{\mu}_{k}}\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$
$\displaystyle\Leftrightarrow$
$\displaystyle\quad\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}~{}\phi_{\theta}(\bm{x}_{i})-\bm{\mu}_{k}(\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik})\in\partial_{\bm{\mu}_{k}}\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$
$\displaystyle\Leftrightarrow$
$\displaystyle\quad\frac{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}~{}\phi_{\theta}(\bm{x}_{i})}{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}}-\bm{\mu}_{k}\in\partial_{\bm{\mu}_{k}}\frac{1}{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}}\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$
$\displaystyle\Leftrightarrow$
$\displaystyle\quad\frac{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}~{}\phi_{\theta}(\bm{x}_{i})}{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}}-\bm{\mu}_{k}\in\partial_{\bm{\mu}_{k}}\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$
$\displaystyle\Leftrightarrow$
$\displaystyle\quad\bm{\mu}_{k}=\text{Proj}_{\mathcal{B}_{2}}(\frac{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}~{}\phi_{\theta}(\bm{x}_{i})}{\sum_{i=1}^{|\mathbb{S}|+|\mathbb{Q}|}\xi_{i}z_{ik}})$

where the penultimate step holds because
$\lambda\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})=\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$
by definition of $\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$, and the last
step holds because the projection operator
$\text{Proj}_{\mathcal{B}_{2}}(\bm{\mu}_{k})=\frac{\bm{\mu}_{k}}{||\bm{\mu}_{k}||}$
is the proximity operator of the constraint function
$\mathcal{L}_{\mathcal{B}_{2}}(\bm{\mu}_{k})$.

##  Appendix C Metrics

Here we provide some details about the metrics used in Section 5

Acc: the classification accuracy on the closed-set instances of the query set
(_i.e_. $y^{q}\in\mathbb{C_{S}}$).

AUROC: the area under the ROC curve is an almost mandatory metric for any OOD
detection task. For a set of outlier predictions in $[O,1]$ and their ground
truth ($0$ for inliers, $1$ for outliers), any threshold $\gamma\in[O,1]$
gives a true positive rate $\textit{TP}(\gamma)$ (_i.e_. recall) and a false
positive rate $\textit{FP}(\gamma)$. By rolling this threshold, we obtain a
plot of TP as a function of FP _i.e_. the ROC curve. The area under this curve
is a measure of the discrimination ability of the outlier detector. Random
predictions lead to an AUROC of $50\%$.

AUPR: the area under the precision-recall (PR) curve is also a common metric
in OOD detection. With the same principle as the ROC curve, the PR curve plots
the precision as a function of the recall. Random predictions lead to an AUPR
equal to the proportion of outliers in the query set _i.e_. $50\%$ in our set-
up.

<EMAIL_ADDRESS>the precision at $90\%$ recall is the achievable precision on the
few-shot open-set recognition task when setting the threshold allowing a
recall of $90\%$ for the same task. While AUROC and AUPR are global metrics,
<EMAIL_ADDRESS>measures the ability of the detector to solve a specific problem,
which is the detection of almost all outliers (_e.g_. for raising an alert
when open-set instances appear so a human operator can create appropriate new
classes). Since all detectors are able to achieve high recall with a
sufficiently permissive threshold $\gamma$, an excellent way to compare them
is to measure the precision of the predictor at a given level of recall
(_i.e_. the proportion of false alarms that the human operator will have to
handle). Random predictions lead to a<EMAIL_ADDRESS>equal to the proportion of
outliers in the query set _i.e_. $50\%$ in our set-up.

##  Appendix D Broad Open-Set setting

As we state in Section 5, in the standard FSOSR setting [16, 21]:

  * •

support sets contain $|\mathbb{C}_{\text{CS}}|=5$ closed-set classes with 1 or
5 instances, or shots, per class;

  * •

query sets are formed by sampling 15 instances per class, from a total of ten
classes:

    * –

the five closed-set classes $\mathbb{C}_{\text{CS}}$;

    * –

an additional set of $|\mathbb{C}_{\text{OS}}|=5$ open-set classes.

This is a very strong assumption on the distribution of open-set samples.
While this will not affect inductive method, it is likely to impact the
performance of transductive methods like OSLO. In this section, we provide
additional results in a more realistic setting. In this new setting, the query
set is formed by sampling 15 instances for each of the 5 closed-set classes,
plus $5\times 15=75$ open-set instances, which are sampled indifferently from
all remaining classes in the test set.

Results in Figure 5 show that the distribution of open-set queries is indeed a
major factor in both closed-set and open-set performances for most
transductive methods. Interestingly enough, some methods like Laplacian Shot
[50] or BDCSPN [23] benefit from this relaxation of the previous open-set
assumption. However, while OSLO’s closed-set accuracy increases in the new
setting, its open-set recognition ability decreases (while still achieving the
best results across the benchmark).

Figure 5: Performance of transductive methods in the broad open-set setting.
We study the closed-set (accuracy) and open-set (AUROC) performance of
transductive methods depending on the size of the query set on mini-ImageNet
in the 1-shot and 5-shot settings. We add the inductive method $k$-NN +
SimpleShot to compare with a method that is by nature independent to the
number of queries.

##  Appendix E The difficulty of FSOSR

As stated in Section 3, our method follows the model-agnostic setting.
Therefore, we perform Few-Shot Open-Set Recognition on features lying in a
feature space $\mathcal{Z}$ and extracted by a frozen model
$\phi_{\bm{\theta}}:\mathcal{X}\rightarrow\mathcal{Z}$, whose parameters
$\bm{\theta}$ were trained on some large dataset
$\mathcal{D}_{base}=\\{(\bm{x}^{b}_{i},y^{b}_{i})\\}_{i=1...|\mathcal{D}_{base}|}$
such that for all $i$, $y^{b}_{i}\in\mathbb{C}_{base}$ with
$\mathbb{C}_{base}\cap\mathbb{C}_{\text{CS}}=\mathbb{C}_{base}\cap\mathbb{C}_{\text{OS}}=\emptyset$.

While model-agnosticity is a very strong selling point for a few-shot learning
method, it also comes with very difficult challenges, especially for an
outlier detection task. In this section, we aim at providing a better
understanding of the difficulty of FSOSR with both a qualitative and
quantitative study of the clusters formed by novel classes
$\mathbb{C}_{\text{OS}}$ when embedded by a feature extractor
$\phi_{\bm{\theta}}$ untrained on $\mathbb{C}_{\text{OS}}$.

Figure 6: 2-dimensional reduction with T-SNE of feature extracted from
ImageNet’s validation set using a ResNet12 trained on miniImageNet. (Left):
images from 20 randomly selected classes represented in miniImageNet’s base
set. (Right): Images from the 20 classes represented in miniImageNet’s test
set. Each color corresponds to a distinct class.

Measuring the difficulty of outlier detection on novel classes. As an anomaly
detection problem, open-set recognition consists in detecting samples that
differ from the population that is known by the classification model. However,
in FSOSR, neither closed-set classes nor open-set classes have been seen
during the training of the feature extractor _i.e_.
$\mathbb{C}_{base}\cap\mathbb{C}_{\text{CS}}=\mathbb{C}_{base}\cap\mathbb{C}_{\text{OS}}=\emptyset$.
In that sense, both the inliers and the outliers of our problem can be
considered outliers from the perspective of the feature extractor.
Intuitively, this makes it harder to detect open-set instances, since the
model doesn’t know well the distribution from which they are supposed to
diverge. Here we empirically demonstrate and quantify the difficulty of OSR in
a setting where closed-set classes have not been represented in the training
set. Specifically, we estimate the gap in terms of quality of the classes’
definition in the feature space, between classes that were represented during
the training of the feature extractor _i.e_. $\mathbb{C}_{base}$, and the
classes of the test set, which were not represented in the training set. To do
so, we introduce the novel Mean Imposture Factor measure and use the intra-
class to inter-class variance ratio $\rho$ as a complementary measure. Note
that the following study is performed on whole datasets, not few-shot tasks.

Mean Imposture Factor (MIF). Let
$\mathcal{D}_{\phi_{\theta}}\subset\mathcal{Z}\times\mathbb{C}$ be a labeled
dataset of extracted feature vectors, with $\phi_{\bm{\theta}}$ a fixed
feature extractor and $\mathbb{C}$ a finite set of classes. For any feature
vector $\bm{z}$ and a class $k$ to which $\bm{z}$ does not belong, we define
the Imposture Factor $\textit{IF}_{\bm{z}|k}$ as the proportion of the
instances of class $k$ in $\mathcal{D}_{\phi_{\theta}}$ that are further than
$\bm{z}$ from their class centroid. Then the MIF is the average IF over all
instances in $\mathcal{D}_{\phi_{\theta}}$.

$\displaystyle\boxed{\textit{MIF}=\frac{1}{|\mathbb{C}|}\sum_{k}\frac{1}{|\mathcal{D}_{\phi_{\theta}}\backslash\mathcal{D}_{k}|}\sum_{\bm{z}\notin\mathcal{D}_{k}}\textit{IF}_{\bm{z}|k}}$
(7) with
$\displaystyle\textit{IF}_{\bm{z}|k}=\frac{1}{|\mathcal{D}_{k}|}\sum_{\bm{z}^{\prime}\in\mathcal{D}_{k}}\mathbbm{1}_{\|\bm{z}^{\prime}-\bm{\mu}_{k}\|_{2}>\|\bm{z}-\bm{\mu}_{k}\|_{2}}$

with $\mathcal{D}_{k}$ the set of instances in $\mathcal{D}_{\phi_{\theta}}$
with label $k$, and $\mathbbm{1}$ the indicator function. The MIF is a measure
of how perturbed the clusters corresponding to the ground truth classes are. A
MIF of zero means that all instances are closer to their class centroid than
any outsider. Note that $\text{MIF}=1-\text{AUROC}(\psi)$ where
$\text{AUROC}(\psi)$ is the area under the ROC curve for an outlier detector
$\psi$ that would assign to each instance an outlier score equal to the
distance to the ground truth class centroid. To the best of our knowledge, the
MIF is the first tool allowing to measure the class-wise integrity of a
projection in the feature space. As a sanity check for MIF, we also report the
intra-class to inter-class variance ratio $\rho$, used in previous works [12],
to measure the compactness of a clustering solution.

Table 3: Contrast between datasets made of images from classes represented
(base) or not represented (test) in the feature extractor’s training set, on
three benchmarks and with several backbones (RN12: ResNet12, WRN:
WideResNet1810, ViT, RN50: ResNet50, and MX: MLP-Mixer), following the MIF (in
percents) and the variance ratio ($\rho$). Best result for each column is
shown in bold.

Classes | miniImageNet | tieredImageNet |  ImageNet $\rightarrow$ Aircraft
---|---|---|---
$\rho$ | MIF (%) | $\rho$ | MIF (%) | $\rho$ | MIF (%)
RN12 | WRN | RN12 | WRN | RN12 | WRN | RN12 | WRN | ViT | RN50 | MX | ViT | RN50 | MX
base | 0.93 | 0.84 | 0.89 | 1.03 | 1.09 | 0.78 | 0.78 | 0.81 | 0.96 | 1.36 | 2.54 | 0.09 | 0.29 | 0.31
test | 2.10 | 2.07 | 5.56 | 7.36 | 2.10 | 1.54 | 4.39 | 5.18 | 3.20 | 4.88 | 5.35 | 18.08 | 21.58 | 17.27

Base classes are better defined than test classes. We experiment on three
widely used Few-Shot Learning benchmarks: miniImageNet [39], tieredImageNet
[27], and ImageNet $\rightarrow$ Aircraft [24]. We use the validation set of
ImageNet in order to obtain novel instances for ImageNet, miniImageNet, and
tieredImageNet’s base classes. We also use it for test classes for
consistency. In Figure 6, we present a visualization of the ability of a
ResNet12 trained on miniImageNet to project images of both base and test
classes into clusters. While we are able to obtain well-separated clusters for
base classes after the 2-dimensional T-SNE reduction, this is clearly not the
case for test classes, which are more scattered and overlapping. Such results
are quantitatively corroborated by Table 3, which shows that both MIF and
$\rho$ are systematically lower for base classes across 3 benchmarks and 5
feature extractors. This demonstrates the difficulty of defining in the
feature space the distribution of a class that was not seen during the
training of the feature extractor, and therefore the difficulty of defining
clear boundaries between inliers and outliers _i.e_. closed-set images and
open-set images, all the more when only a few samples are available.

##  Appendix F Additional results

Figure 7: Version of Fig. 3 on mini-ImageNet.

In this section we provide more complete versions of plots included in the
main paper. Fig. 7 shows the results depending on the size of the query set
for mini-ImageNet. Furthermore, 8 and 9 complete Fig. 2, showing the
additional<EMAIL_ADDRESS>metric, along with the results on the WRN2810 provided by
[46].

Figure 8: Complete version of Fig. 2 with a ResNet-12. (Left column): 1-shot.
(Right column): 5-shot.

Figure 9: Complete version of Fig. 2 with a WideResNet 28-10. (Left column):
1-shot. (Right column): 5-shot. SnatcherF was not included in this plot
because a yet misdiagnosed problem occurred with the provided tiered-ImageNet
checkpoint.


#  navyblue Geographic Difference-in-Discontinuities

https://kylebutts.com/Kyle Butts University of Colorado Boulder, Economics
Department (mailto:kyle.butts<EMAIL_ADDRESS>
A recent econometric literature has critiqued the use of regression
discontinuities where administrative borders serves as the ‘cutoff’.
Identification in this context is difficult since multiple treatments can
change at the cutoff and individuals can easily sort on either side of the
border. This note extends the difference-in-discontinuities framework
discussed in Grembi et al. (2016) to a geographic setting. The paper
formalizes the identifying assumptions in this context which will allow for
the removal of time-invariant sorting and compound-treatments similar to the
difference-in-differences methodology.

Keywords: difference-in-discontinuities, spatial econometrics, sorting,
compound treatment, causal inference

JEL Classification Number: C01, R15, R58

## 1 — Introduction

An increasingly popular estimation strategy involves using administrative
borders as cutoffs in a regression discontinuity (RD) setting where the
‘running variable’ is the distance to the border. The purpose of using
observations close to the border ‘cutoff’ is to try and better match treated
and control units based on unobservable characteristics. Identification using
the standard RD continuity assumption is problematic because many laws and
institutions change discontinuously (i.e. compound treatment) at the border
cutoff and people chose to sort on either side of the borders (i.e. sorting
around cutoff), leading to important differences between units in close
geographic proximity even in the counterfactual world without
treatment.111Identification through randomization local to the cutoff does not
make sense in the geographic context because that would require people to
randomly be located on either side of the border.

The intuition of the difference-in-discontinuities design is very similar to
the difference-in-differences design. A pre-treatment RD identifies time-
invariant effects of other laws as well as the discontinuity in outcomes due
to time-invariant sorting. A post-treatment RD identifies those previous two
discontinuities plus the one caused by the treatment of interest. The
difference between the two identifies the treatment effect. In this note, I
extend the difference-in-discontinuities identification strategy formalized in
Grembi et al. (2016) to the context of geographic RDs and discuss the
particular identifying assumptions needed for the above identification sketch
to be true when using a geographic RD.

Figure 1 shows a stylized example of this identification. The left panel shows
a discontinuity at the border cutoff that exists prior to treatment. This
could be due to other policies changing at the border or sorting due to other
reasons. The right panel shows the treated and untreated potential outcomes in
the post-period. The key idea behind the diff-in-disc estimator is that the
pre-period discontinuity can be estimated and removed from the second period
discontinuity to estimate the treatment effect.

Figure 1: Example of Diff-in-Disc Identification

_Notes:_ This figure shows a stylized example of identification in the diff-
in-disc setting.

I contribute to the econometric literature on RD in three ways. First, I
contribute to the nascent literature formalizing the difference-in-
discontinuities identification strategy (Grembi et al., 2016; Galindo-Silva et
al., 2021; Millán-Quijano, 2020). The results of the previous papers only
consider the case of compound treatment where multiple treatment occurs at a
cutoff. This paper formalizes the effectiveness of using difference-in-
discontinuities to address the problem of time-invariant sorting around the
cutoff.

The second contribution is that I extend on the work of Keele and Titiunik
(2015) who formalize identification with geographic RDs into the _geographic_
difference-in-discontinuities setting. The authors raise the problem of
sorting on either side of the boundary as well as multiple laws changing
discontinuously at the boundary and propose stringent assumptions to avoid
these problems in the cross-section. This paper uses the difference-in-
discontinuities methodology which provide a solution to these problems under
arguably less stringent assumptions by leveraging the panel nature of data to
estimate time-invariant sorting and effects of other policy/institution
changes.

Last, I show that that estimation of difference-in-discontinuities with panel
data can be done by running RD on outcomes that have been first-differenced.
This allows for the use of modern advancements in estimation and inference of
RDs.222See Cattaneo et al. (2019) and Cattaneo et al. (2199) for an overview
of modern techniques. The formulation using first-differences is practically
useful as estimation can be done using the suite of RD packages found at
https://rdpackages.github.io/. In cases where panel data is not available,
then the local regression framework proposed in Grembi et al. (2016) can be
used.

## 2 — Methods

### 2.1. Traditional RD Identification

Before introducing the difference-in-discontinuities method, I first review
geographic RD to highlight difficulties in cross-sectional identification. I
consider the standard context a random iid sample of units $i\in\\{1,\dots
n\\}$. There is a running variable $D_{i}$ that measures distance to the
border of a treated area. Without loss of generality, the distance is
normalized to zero with positive distances being within the treatment
area.333Keele and Titiunik (2015) discuss the choice of using a single measure
of distance versus a two-dimensional running variable. The difference-in-
discontinuity method can be extended into the two-dimensional framework
easily, but data will usually render the two-dimensional case implausible. The
observed outcome is modeled by

$y_{i}=f(D_{i})+\tau(D_{i})\mathbf{1}(D_{i}\geq
0)+\underbrace{X_{i}\beta+u_{i}}_{\equiv\varepsilon_{i}}.$

The function $f(D)$ summarizes location-specific characteristics that affect
outcomes. For example, one variable could be proximity to a city and $f(D)$
summarizes its effect on the outcome variable. More generally, $f(D)$ captures
amenities and labor markets as they change across space. On the other hand,
$\varepsilon_{i}$ represents the _potentially_ unobserved individual-specific
characteristics that affect outcome variable. The quantity
$Y_{i}(0)=f(D_{i})+\varepsilon_{i}$ determines the outcome variable in the
absense of treatment and $\tau(D_{i})$ is the average treatment effect at
distance $D_{i}$.

Identification of the treatment effect relies on the assumption that location-
specific and individual-specific characteristics evolve smoothly across the
border:

######  Assumption 1 (RD).

  * (i)

The functions $f(D)$ and $\tau(D)$ are continuous at the cutoff, $D=0$,

  * (ii)

$\mathbb{E}\left[\varepsilon_{i}|D_{i}=D\right]$ is continuous at the cutoff,
$D=0$.

Part (i) of ( (RD).) says that the effect of the running variable on the
outcome with and without treatment is continuous at the cutoff and part (ii)
says that the effect of other _potentially_ unobserved individual-specific
variables on the outcome are continuous at the cutoff. In the context of
geographic discontinuities, a discontinuity in $f(D)$ could arise from
multiple policies changing at the border and a discontinuity in
$\mathbb{E}\left[\varepsilon_{i}|D_{i}=D\right]$ could arise from sorting
across the border (Keele and Titiunik, 2015). These two problemsrepresent a
central threat to identification of treatment effects in the geographic RD
setting.

If the two continuity assumptions are satisfied, observations in the control
area close to the border identify the limiting value of $f(0)$ and
observations in the treated area close to the border identify the limiting
value of $f(0)+\tau(0)$. The difference between these two limits identify
$\tau(0)$. Formally, for a variable $z$, the left and right limits at the
cutoff are denoted $z^{+}\equiv\lim_{D_{i}\to 0^{+}}z_{i}$ and
$z^{-}\equiv\lim_{D_{i}\to 0^{-}}z_{i}$. With ( (RD).), it is easy to show
that the RD estimate identifies the treatment effect, i.e.
$\tau=y^{+}-y^{-}$.444See Theorem 1 in Hahn et al. (2001).

######  Theorem 1 (RD Identification).

Under ( (RD).), $\tau(0)=y^{+}-y^{-}$.

### 2.2. Difference-in-Discontinuities Identification

Now we turn to the panel setting where we observe outcomes before and after
treatment occurs, $t\in\\{0,1\\}$. We observe a random iid panel sample of
$\left\\{(y_{i0},y_{i1},D_{i})\right\\}_{i=1}^{n}$. In this setting,
discontinuities at the border before treatment informs us on the affects of
other treatments and time-invariant sorting. Potential outcomes for individual
$i$ at time $t$ are now modeled as

$y_{it}=f_{t}(D_{i})+\gamma(D_{i})\mathbf{1}(D_{i}\geq
0)+\tau(D_{i})\mathbf{1}(D_{i}\geq 0)\mathbf{1}(t=1)+\varepsilon_{it},$ (1)

where $\gamma(D)$ represent the time-invariant discontinuity at the cutoff
which could be due to time-invariant sorting and/or the effects of other
policies that change at the border; the untreated location-specific component,
$f_{t}(D)$, can very across periods; and $\tau(D)$ remains the treatment
effect of interest.

The assumptions necessary to identify the treatment effect $\tau(0)$ requires
the traditional RD assumptions to hold in both periods.

######  Assumption 2 (Diff-in-Disc).

  * (i)

The functions $f_{0}(D),f_{1}(D),$ and $\tau(D)$ are continuous at $D=0$,

  * (ii)

$\mathbb{E}\left[\varepsilon_{it}|D_{i}=D\right]$ is continuous at the cutoff,
$D=0$, for $t\in\\{0,1\\}$.

These assumptions warrant a bit of discussion. Note that the continuity
assumption on $f_{0}$ is mild because discontinuities from compound treatment
and time-invariatn sorting are allowed in $\gamma(D)$. This is an improvement
over traditional geographic RDs which require these effects to not be present
(Keele and Titiunik, 2015).555This is similar to the difference-in-differences
methodology that allows for time-invariant differences in levels. In the post
period, ( (Diff-in-Disc).) requires two things. First, $f_{1}(D)$ being
continuous requires that no other policies turn on between periods that would
cause a discontinuity at the border. Second, it requires that the effects of
previous policies were already fully developed in period 0. If the effects of
other policies change over time, then the changes in effects over time would
not be absorbed by $\gamma(D)$ and would cause a discontinuity in $f_{1}(D)$
that would be mistaken as the treatment effect. Second, part (ii) requires
that no additional sorting can occur between 0 and 1, whether that be due to
treatment or lagged sorting from previous treatments.

To help with estimation of the treatment effect, we can reformulate our
potential outcomes in a first-difference model,

$(y_{1}-y_{0})=(f_{1}(D_{i})-f_{0}(D_{i}))+\tau(D_{i})\mathbf{1}(D_{i}\geq
0)+(\varepsilon_{i1}-\varepsilon_{i0}),$

where $\gamma(D_{i})$ cancels out because it is time-invariant.

######  Theorem 2 (Diff-in-Disc Identification).

Under ( (Diff-in-Disc).), $\tau(0)=(y_{1}-y_{0})^{+}-(y_{1}-y_{0})^{-}$.

###### Proof.

$\displaystyle(y_{1}-y_{0})^{+}-(y_{1}-y_{0})^{-}$
$\displaystyle=\tau(D)^{+}+(f_{1}-f_{0})^{+}+(\varepsilon_{i1}-\varepsilon_{i0})^{+}-((f_{1}-f_{0})^{-}+(\varepsilon_{i1}-\varepsilon_{i0})^{-})$
$\displaystyle=\tau(0)+(f_{1}^{+}-f_{1}^{-})+(f_{0}^{+}-f_{0}^{-})+(\varepsilon_{1}^{+}-\varepsilon_{1}^{-})+(\varepsilon_{0}^{+}-\varepsilon_{0}^{-})$
$\displaystyle=\tau(0),$

where the second equality comes from continuity of $\tau(D)$ and the last
equality comes from the two continuity assumptions. ∎

The above theorem says that so long as sorting and other policies are fully
observed in the pre-period, a regression discontinuity estimated on a first-
differenced outcome will identify the treatment effect. This theorem is
closely related to Grembi et al. (2016) but differs in an important way.
First, they find that $\tau(0)=(y_{1}^{+}-y_{1}^{-})-(y_{0}^{+}-y_{0}^{-})$
which does not require panel data. In cases of panel data, formulating the
above identification result in terms of first differences is advantageous.
Since $(y_{1}-y_{0})^{+}-(y_{1}-y_{0})^{-}$ is a standard RD estimate of the
difference between the right and left limits, this unlocks the wide set of
econometric tools used in RD estimation including local polynomial regression,
data-driven bandwidth selection, and bias-corrected inference. Cattaneo et al.
(2019) and Cattaneo et al. (2199) provide a literature review of the modern RD
literature and include a set of R and Stata programs containing powerful
estimation tools.

In the non-panel case, estimation can proceed in a local-polynomial regression
framework as proposed by Grembi et al. (2016). They recommend running the
following regression using observations within a small interval around
$D_{i}=0$:

$\displaystyle Y_{it}$
$\displaystyle=\delta_{0}+\delta_{1}*D_{i}+\mathbf{1}(D_{i}\geq
0)\left(\gamma_{0}+\gamma_{1}D_{i}\right)+$
$\displaystyle\quad\mathbf{1}(t=1)\left(\alpha_{0}+\alpha_{1}*D_{i}+\mathbf{1}(D_{i}\geq
0)\left(\beta_{0}+\beta_{1}D_{i}\right)\right]+\eta_{it}.$

From standard regression results, $\beta_{0}$, will be the difference-in-
discontinuities estimate. This estimation strategy, however, does not as
easily allow for the use of modern bias-robust estimators.

## 3 — Discussion

This paper extended the difference-in-discontinuities framework proposed by
Grembi et al. (2016) into the context of geographic discontinuities. This
setting faces the same problem of compound treatment that other RD contexts
exhibit and since individuals can sort sort across the border, this context
provides additional difficulties. This paper formalizes the necessary
assumptions in the _geographic_ context in order to identify the treatment
effect of a policy. Moreover, in the presence of panel data, this paper
proposes improved estimation techniques by recasting the estimator as a RD
estimator on first-differenced data.

## References

  * (1)
  * Cattaneo et al. (2019) Cattaneo, Matias D., Nicolas Idrobo, and Rocio Titiunik. 2019\. “A Practical Introduction to Regression Discontinuity Designs: Foundations.” arXiv:1911.09511 [econ, stat].  10.1017/9781108684606, arXiv: 1911.09511.
  * Cattaneo et al. (2199) Cattaneo, Matias D, Nicolas Idrobo, and Rocıo Titiunik., “A Practical Introduction to Regression Discontinuity Designs: Volume II.” 106.
  * Galindo-Silva et al. (2021) Galindo-Silva, Hector, Nibene Habib Some, and Guy Tchuente. 2021\. “Fuzzy Difference-in-Discontinuities: Identification Theory and Application to the Affordable Care Act.” arXiv:1812.06537 [econ], http://arxiv.org/abs/1812.06537, arXiv: 1812.06537.
  * Grembi et al. (2016) Grembi, Veronica, Tommaso Nannicini, and Ugo Troiano. 2016\. “Do Fiscal Rules Matter?” American Economic Journal: Applied Economics 8 (3): 1–30.  10.1257/app.20150076.
  * Hahn et al. (2001) Hahn, Jinyong, Petra Todd, and Wilbert Klaauw. 2001\. “Identification and Estimation of Treatment Effects with a Regression-Discontinuity Design.” Econometrica 69 (1): 201–209.  10.1111/1468-0262.00183.
  * Keele and Titiunik (2015) Keele, Luke J., and Rocío Titiunik. 2015\. “Geographic Boundaries as Regression Discontinuities.” Political Analysis 23 (1): 127–155.  10.1093/pan/mpu014.
  * Millán-Quijano (2020) Millán-Quijano, Jaime. 2020\. “Fuzzy difference in discontinuities.” Applied Economics Letters 27 (19): 1552–1555.  10.1080/13504851.2019.1696930.