11institutetext:  1Department of Biomedical Engineering, University of Basel,
Allschwil, Switzerland
2Department of Neurology, University Hospital Basel, Basel, Switzerland
3Department of Radiology, University Hospital Basel, Basel, Switzerland
4MIAC AG, Basel, Switzerland
*S. Andermatt and S. Pezold contributed equally.

# Multi-dimensional Gated Recurrent Units for Automated Anatomical Landmark
Localization

Simon Andermatt*,1 Simon Pezold*,1 Michael Amann2,3,4 Philippe C. Cattin1

###### Abstract

We present an automated method for localizing an anatomical landmark in three-
dimensional medical images. The method combines two recurrent neural networks
in a coarse-to-fine approach: The first network determines a candidate
neighborhood by analyzing the complete given image volume. The second network
localizes the actual landmark precisely and accurately in the candidate
neighborhood. Both networks take advantage of multi-dimensional gated
recurrent units in their main layers, which allow for high model complexity
with a comparatively small set of parameters. We localize the medullopontine
sulcus in 3D magnetic resonance images of the head and neck. We show that the
proposed approach outperforms similar localization techniques both in terms of
mean distance in millimeters and voxels w.r.t. manual labelings of the data.
With a mean localization error of $1.7\text{\,}\mathrm{mm}$, the proposed
approach performs on par with neurological experts, as we demonstrate in an
interrater comparison.

##  1 Introduction

Localizing anatomical landmarks is a common task in many medical applications.
Finding matching anatomical points in images may be necessary for seeding a
segmentation algorithm, for registration problems, or for providing points of
reference for quantitative measurements. Although finding landmarks in
volumetric images is error-prone and time-consuming, the task is often still
carried out manually. Using a fully automated approach mitigates the inter and
intra-rater variability through an objective and efficient process without
manual interference. Therefore, many automated localization methods have been
proposed, with varying degrees of robustness, reliability, and generalization
potential. Some of the methods, such as Bhanu Prakash et al. [2] or Elattar et
al. [3], use very basic image processing techniques, but many others rely on
concepts from machine learning: for example, for localizing landmarks in the
brain, Guerrero et al. [6] use manifold learning and O’Neil et al. [9] use
random forests; for cardiac landmark localization, Karavides et al. [7] use
Adaboost and Lu and Jolly [8] use probabilistic boosting trees; Xue et al.
[11] use boosting for localizing landmarks on the knee joint. For a recent
overview, also see Zhou et al. [15].

In recent years, ground-breaking advancements using neural networks have been
achieved in various domains, allowing for automatic learning of discriminative
features for the problem at hand and avoiding the need for manually designed
(often called handcrafted) features. Consequently, these techniques have also
found their way into landmark localization. Examples are Zheng et al. [14],
who use two neural networks successively to localize the carotid bifurcation
in 3D CT images, Ghesu et al. [4], who propose a so-called artificial agent
for localizing various anatomical landmarks in 2D and 3D images of different
modalities, and Yang et al. [12], who apply convolutional neural networks for
landmark localization on the femur in MR images.

Existing approaches based on convolutional neural networks (CNNs) are capable
of detecting very delicate structure, yet are limited to the local
neighborhood of the filters used in each layer of the network. Using a
recurrent neural network (RNN) for this task allows for flexible feature
relationships of varying length and scale. This is especially useful given a
localization task, where the surrounding tissues structure can take a number
of different shapes and sizes. Tackling volumetric data with RNNs for
_segmentation_ has been recently demonstrated by Andermatt et al. [1] with
multi-dimensional gated recurrent units (MD-GRUs). To our knowledge, neither
multi-dimensional RNN nor MD-GRUs have been applied to the task of _landmark
localization_ so far.

In this paper, we propose to apply MD-GRUs in a two-stage approach to the task
of anatomical landmark localization. In the first stage, the anatomical region
of interest is roughly located in the given image volume. We then determine
the actual landmark coordinate in a subvolume in the second stage. We apply
the proposed method to 3D MR images of the head and neck, in which we locate
the medullopontine sulcus, and compare the found coordinates to those of
manual labels. Our results from an interrater comparison suggest that the
proposed method cannot be distinguished from a clinical expert.

##  2 Methods

Figure 1: Localization network. a) Coarse approximation of landmark
coordinates in subsampled low resolution representation of full data. b) Fine
approximation of landmark coordinates in extracted window around detected
coarse location in a second localization network. Both networks use the
architecture depicted at the bottom.

For the accurate localization of landmarks, we propose to use two separate
localization networks of similar structure, to both accelerate the process and
allow for a decently complex network. Both localization networks work on the
same number of voxels – in our case we fixed it to $64^{3}$ voxels – and find
the coordinate in said volume which lies closest to the true landmark. The
first network is provided data subsampled to such a degree, that the full
original volume can be represented inside of it. The network will then
approximate a location, which will in turn be used to sample a subvolume at
the original resolution from the image data around the found location. In our
case, the first network is provided with 4-fold subsampled data and the second
processes data at the original resolution, centered at the location which was
found by the first network.

###  2.0.1 Subsampling MD-GRU Layer

We propose to adapt the MD-GRU layer [1], which was introduced to handle
segmentation problems, to the application of landmark localization. In order
to do so, we implement the ability to subsample at each MD-GRU layer and hence
at each convolutional gated recurrent unit (C-GRU) which it consists of. This
effectively reduces the spatial problem size, allowing a multi-resolution
processing approach. We adjust the original C-GRU equations as follows:

$\displaystyle
f^{j}(t,\alpha,\beta)=\sum_{i}^{I}x_{t}^{i}\star\alpha^{i,j}+\beta^{j},\hskip
20.00003pt$ $\displaystyle
g^{j}(t,\alpha)=\sum_{k}^{J}h_{t-1}^{k}*\alpha^{k,j},$ (1) $\displaystyle
r_{t}^{j}=\sigma(f^{j}(t,w_{r},b_{r})+g^{j}(t,u_{r})),\hskip 20.00003pt$
$\displaystyle z_{t}^{j}=\sigma(f^{j}(t,w_{z},b_{z})+g^{j}(t,u_{z})),$ (2)
$\displaystyle\tilde{h}^{j}_{t}=\phi(f^{j}(t,w,b)+r_{t}^{j}\odot
g^{j}(t,u)),\hskip 20.00003pt$ $\displaystyle h^{j}_{t}=z_{t}^{j}\odot
h^{j}_{t-1}+(1-z_{t}^{j})\odot\tilde{h}^{j}_{t},$ (3)

where $x_{t}^{\cdot}$, $h_{t}^{\cdot}$ denote the input and state of the C-GRU
at time $t$, and $i$, $j$, $k$ denote the respective channels. The operator
$\odot$ denotes elementwise multiplication, as in [1]. Variables $u$, $w$, and
$b$ are trainable weights. We call $\tilde{h}$ in Eq. (3) the proposal and $r$
and $z$ in Eqs. (2) the reset and update gate.

We accomplish subsampling by introducing strided convolutions, which are
denoted as $\star$ in Eq. (1). The size of the state as well as of all the
gates and the proposal will be reduced by the factor of the chosen stride $S$
per spatial dimension. Each C-GRUs’ output is then subjected to one-
dimensional average pooling, compressing the time dimension by stride $S$. The
sum of all $d$ compressed C-GRU results $\hat{h}$ yields the MD-GRU output
$H$:

$\displaystyle H^{j}=\sum_{d}\hat{h}^{j},\hskip
20.00003pt\hat{h}^{j}_{t^{\prime}}=\frac{1}{S}\sum\limits_{s=0}^{S-1}h^{j}_{St^{\prime}+s}.$
(4)

###  2.0.2 Localization Network

At the core, we use the same localization network for all experiments. We use
three subsequent compositions of a subsampling MD-GRU layer, a voxelwise fully
connected layer, and a tanh activation function. The subsampling MD-GRU layers
are provided with 32, 64, and 128 channels, respectively. All of them use
strides of 2 along spatial dimensions, the volume is hence subsampled 8-fold
at each composition. We use DropConnect [10] with a drop rate of 0.5 on the
input convolution filters of both gates $r^{j},\,z^{j}$ and the proposal
$\tilde{h}$. The voxelwise fully connected layers are realized through
convolution layers with spatial filters of $1^{3}$, with 48, 96, and 192
channels each.

The resulting subvolume is of size
$\nicefrac{{N_{x}}}{{8}}\times\nicefrac{{N_{y}}}{{8}}\times\nicefrac{{N_{z}}}{{8}}$,
given the input shape was $(N_{x}\times N_{y}\times N_{z})$. The subvolume is
reshaped into a vector, in which we process each coordinate by two fully
connected layers of $(C_{x}+C_{y}+C_{z})\cdot 4$ and $(C_{x}+C_{y}+C_{z})$
layers, which are connected through a leaky rectifying unit defined as
$\text{lrelu}(x)=\max\\{0.01\,x,\>x\\}$. The resulting vector is split into
three separate vectors of sizes $C_{x}$, $C_{y}$, and $C_{z}$, where $C_{.}$
gives the number of possible coordinate positions along the respective
dimension. These are then fed into individual softmax activation functions to
estimate the probabilities for each coordinate in each vector. We use the sum
of all cross entropy losses as loss function for the entire network. Figure 1
shows an overview of the network architecture.

###  2.0.3 Subsampling

In the first stage, we use a strided convolution on the input to match the
localization networks input resolution. We pad the input, such that the shape
of the volume is a multiple of the required shape for the localization
network. In our case, we padded the data to $256^{3}$ and used strides $S$ of
4 with a filter size of $S\cdot 2+1$ and 16 channels for the convolution
layer.

###  2.0.4 Superresolution

Our method, as explained so far, is restricted to voxel coordinates, since we
estimate with our method discrete instead of continuous coordinates. In the
following, we explain two extensions to our idea to yield superresolution
results.

The first extension takes advantage of the coordinate resolution-independent
formulation in the _Localization Network_ paragraph above. Instead of
estimating as many classes for each of the three coordinates as there are
voxels in the respective dimension in the volume, we estimate $n$ times the
amount. This allows us to estimate values which are $\nicefrac{{1}}{{n}}$
voxels apart and hence allow for a more fine-grained localization. In our
experiments, we use $n=4$ resulting in 256 classes.

Our second idea exploits neighborhood information in our coordinate
probability vectors by fitting a parabola to the largest probability and its
two neighbors per coordinate. The maxima of these functions can then be
interpreted as our coordinate location. This allows for an even finer
localization, but is based and hence limited on the chosen number of
coordinate probabilities.

###  2.0.5 Optimization

We trained each localization network together with their subsampling addition
individually. All networks were trained for a total of 50 epochs, where one
epoch comprised one random sample from each training subject, which led to a
total of 50 200 iterations. We used AdaDelta [13] with a learning rate of
0.001. We initialized all weights of the convolutions with the method of
Glorot and Bengio [5], the biases with zero and the fully connected layers at
the end of the localization network with random values from
$[-\nicefrac{{\sqrt{3}}}{{N_{i}}},+\nicefrac{{\sqrt{3}}}{{N_{i}}}]$, where
$N_{i}$ is the number of input units. For the first network, we sampled from
the center of the padded volume with a random offset in the range of
$[-100,100]$ voxels per coordinate; for the second network, we just required
that the training landmark was within the volume. The training loss is
visualized in Fig. 2.

Figure 2: Cross entropy loss. Mean $\pm$ one standard deviation on training
and validation set for the 3 trained networks, smoothed using a gaussian for
visualization.

For preprocessing, we apply a high-pass filter on the input, the results of
which we use together with the original data as input to our networks.
Additionally, we normalize to zero mean and a standard deviation of one for
each of the input volumes. Apart from this, no preprocessing is required.

##  3 Results

Figure 3: Localization results for rater 1 _(red $\bigtriangledown$)_, rater 2
_(green $\bigtriangleup$)_, and proposed method _(blue $\circ$)_. Shown are
the best three _(left)_ and worst three _(right)_ localizations of the
proposed method wrt. rater 1, both in sagittal _(top)_ and transverse
_(bottom)_ view. Table 1: Localization accuracy and precision. a) Localization
error on the test set when using only the first network (_top row_) and both
networks with a varying number of coordinate classes, with or without parabola
fitting (_bottom row:_ proposed combination); b) localization error on the
test set in comparison to two human raters; c) localization errors reported in
the literature.

a) |  | Error [mm]
---|---|---
|  | Median | Mean | Std.
Coarse localization |  | 4.83 | 5.02 | 2.22
Fine, 64 classes |  | 1.74 | 1.97 | 1.02
Fine+parab., 64 cl. |  | 1.77 | 1.89 | 0.98
Fine, 256 classes |  | 1.47 | 1.72 | 1.03
Fine+parab., 256 cl. |  | 1.40 | 1.69 | 1.02

b) |  | Error [mm]
---|---|---
|  | Median | Mean | Std.
Rater 1 vs. rater 2 |  | 1.39 | 1.59 | 0.98
Proposed vs. rater 1 |  | 1.40 | 1.69 | 1.02
Proposed vs. rater 2 |  | 1.65 | 1.73 | 0.87
Proposed vs. both |  | 1.50 | 1.71 | 0.95

c) |  | Error [mm] |  |  |  |
---|---|---|---|---|---|---
Method |  | Median | Mean | Std. |  | Voxel size [$\text{\,}{\mathrm{mm}}^{3}$] |  | Target landmark
Proposed |  | 1.50 | 1.71 | 0.95 |  | $1.00\times 1.00\times 1.00$ |  | medullopontine sulcus
Zheng et al. [14] |  | 1.21 | 2.64 | 4.98 |  | $0.46\times 0.46\times 0.50$ |  | carotid bifurcation
Ghesu et al. [4] |  | 0.8 | 1.8 | 2.9 |  | $1.00\times 1.00\times 1.00$ |  | carotid bifurcation
Yang et al. [12] |  | — | 4.13 | 1.70 |  | $0.37\times 0.37\times 0.70$ |  | femoral medial distal point
Xue et al. [11] |  | — | 1.41 | 0.91 |  | $0.3\times 0.3\times[0.6,3]$ |  | knee joint (23 landmarks)
Guerrero et al. [6] |  | — | 0.45 | 0.22 |  | — |  | anterior commissure

To evaluate the proposed approach, we located the medullopontine sulcus, a
distinct cavity in the brainstem, in MR images of the head and neck (see Fig.
3). Images were acquired with a T1-weighted MPRAGE sequence, having a
resolution of $1\text{\,}{\mathrm{mm}}^{3}$ and a size between $160\times
240\times$256\text{\,}\mathrm{v}\mathrm{o}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{s}$$
and $192\times
256\times$256\text{\,}\mathrm{v}\mathrm{o}\mathrm{x}\mathrm{e}\mathrm{l}\mathrm{s}$$.
Altogether, we had $1218$ images of $265$ subjects, with a median number of
$5$ images per subject (minimum: $1$, maximum: $8$), which we randomly
assigned to a training set ($1004$ images of $213$ subjects), a validation set
($114$ images of $26$ subjects), and a test set ($100$ images of $26$
subjects), making sure that all images of each subject were assigned to the
same set.

For training and evaluation of the localization, we used manual labels of the
landmark. These labels were provided by clinical expert raters who placed them
on a graphical user interface enabling them to zoom in and out of the imaged
volumes as necessary. To allow for interrater comparisons, we had two raters
place the landmark in all images of the test set.

Training 50 epochs for the coarse and fine networks took around 41 and 34
hours, respectively. Testing, on the other hand, requires less than 2 seconds
for either network, resulting in a total of around 3–4 seconds for
localization. Using our extension of estimating 256 class probabilities
instead of 64 per coordinate requires only 2.5 hours more training time and
took around 2.5 seconds per volume for testing, which results in around 4
seconds in total for localization.

Figure 3 shows our three best and worst localization results. Note that our
largest error (rightmost column in Fig. 3) is actually produced by a
mislabeling of a clinical expert, as can be seen by the off-center position of
the red marker.

Table 1a shows the localization errors when using only the first network as
compared to using both. The second network increases the localization accuracy
notably, as does using more coordinate classes and fitting a parabola.

Table 1b shows the results from comparing both human raters with the proposed
approach. The listed values indicate that our approach almost reaches human
performance: comparing our results to those of a human rater produces
approximately the same error as two human raters compared to each other.

Table 1c shows results for landmark localization reported in the literature.

##  4 Discussion and Conclusion

Our results, as listed in Table 1c, appear competitive: compared to other
neural network approaches [4, 12, 14], mean error and standard deviation are
better in terms of millimeters and voxels. When comparing to Xue et al. [11],
one has to keep in mind their notably higher in-plane resolution. While
Guerrero et al. [6] achieve higher accuracy and precision, a comparison
appears difficult: apart from not stating the voxel size, their method
requires images with similar field of view, which cannot be guaranteed in our
case, as parts of our images are centered on the neck while others are
centered on the head. In any case, caution has to be taken when comparing
these results: on the one hand, evaluated anatomical landmarks, imaging
modalities, and image resolutions differ. On the other hand, our interrater
comparison (recall Table 1b) suggests that there is a lower bound for the
achievable accuracy, which might be well above a given image resolution and
might depend on the particular anatomical landmark. Determining the limit of
actually achievable accuracy of our method would require evaluating data with
lower interrater variability. The results of Xue et al. [11] allow a similar
conclusion, in that their method’s error is similar to the error from their
interrater comparison, as well. Unfortunately, the other authors do not
provide interrater comparisons.

We have shown two ideas that improved our localization results. The
combination of both even surpassed the accuracy of each of them applied
separately. Considering interrater variability, we are still slightly less
accurate than a human rater. We think that this is partly based on the
discrete probability distribution and our sampling technique when training the
algorithm. We randomly sampled subvolumes using integer coordinates during
training since this process does not require interpolation. But this also
means that each training sample could only get mapped on a subset of all
possible coordinate classes.

###  4.0.1 Conclusion

We have shown that the localization of the medullopontine sulcus is
successfully possible using our proposed automated technique, which adapts MD-
GRUs to the task of landmark localization. We introduced a number of
improvements, which all led to even more accurate results without
significantly increasing the training time. Future work will focus on
evaluating our localization approach on multiple anatomical landmarks in
different imaging modalities.

## References

  * [1] Andermatt, S., Pezold, S., Cattin, P.: Multi-dimensional Gated Recurrent Units for the Segmentation of Biomedical 3D-Data. In: International Workshop on Large-Scale Annotation of Biomedical Data and Expert Label Synthesis. pp. 142–151. Springer (2016)
  * [2] Bhanu Prakash, K.N., Hu, Q., Aziz, A., Nowinski, W.L.: Rapid and Automatic Localization of the Anterior and Posterior Commissure Point Landmarks in MR Volumetric Neuroimages. Academic Radiology 13(1), 36–54 (Jan 2006)
  * [3] Elattar, M., Wiegerinck, E., van Kesteren, F., Dubois, L., Planken, N., Vanbavel, E., Baan, J., Marquering, H.: Automatic aortic root landmark detection in CTA images for preprocedural planning of transcatheter aortic valve implantation. The International Journal of Cardiovascular Imaging 32(3), 501–511 (Mar 2016)
  * [4] Ghesu, F.C., Georgescu, B., Mansi, T., Neumann, D., Hornegger, J., Comaniciu, D.: An Artificial Agent for Anatomical Landmark Detection in Medical Images. In: MICCAI 2016. pp. 229–237. Springer, Cham (Oct 2016)
  * [5] Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. In: Aistats. vol. 9, pp. 249–256 (2010)
  * [6] Guerrero, R., Wolz, R., Rueckert, D.: Laplacian Eigenmaps Manifold Learning for Landmark Localization in Brain MR Images. In: MICCAI 2011. pp. 566–573. Springer, Berlin, Heidelberg (Sep 2011)
  * [7] Karavides, T., Leung, K.Y.E., Paclik, P., Hendriks, E.A., Bosch, J.G.: Database guided detection of anatomical landmark points in 3D images of the heart. In: 2010 IEEE International Symposium on Biomedical Imaging: From Nano to Macro. pp. 1089–1092 (Apr 2010)
  * [8] Lu, X., Jolly, M.P.: Discriminative Context Modeling Using Auxiliary Markers for LV Landmark Detection from a Single MR Image. In: Statistical Atlases and Computational Models of the Heart. Imaging and Modelling Challenges. pp. 105–114. Springer, Berlin, Heidelberg (Oct 2012)
  * [9] O’Neil, A., Dabbah, M., Poole, I.: Cross-Modality Anatomical Landmark Detection Using Histograms of Unsigned Gradient Orientations and Atlas Location Autocontext. In: Machine Learning in Medical Imaging. pp. 139–146. Springer, Cham (Oct 2016)
  * [10] Wan, L., Zeiler, M., Zhang, S., Cun, Y.L., Fergus, R.: Regularization of neural networks using dropconnect. In: Proceedings of the 30th International Conference on Machine Learning (ICML-13). pp. 1058–1066 (2013)
  * [11] Xue, N., Doellinger, M., Ho, C.P., Surowiec, R.K., Schwarz, R.: Automatic detection of anatomical landmarks on the knee joint using MRI data. Journal of Magnetic Resonance Imaging 41(1), 183–192 (Jan 2015)
  * [12] Yang, D., Zhang, S., Yan, Z., Tan, C., Li, K., Metaxas, D.: Automated anatomical landmark detection ondistal femur surface using convolutional neural network. In: 2015 IEEE 12th International Symposium on Biomedical Imaging (ISBI). pp. 17–21 (Apr 2015)
  * [13] Zeiler, M.D.: ADADELTA: An Adaptive Learning Rate Method. arXiv:1212.5701 [cs] (Dec 2012)
  * [14] Zheng, Y., Liu, D., Georgescu, B., Nguyen, H., Comaniciu, D.: 3D Deep Learning for Efficient and Robust Landmark Detection in Volumetric Data. In: MICCAI 2015. pp. 565–572. Springer, Cham (Oct 2015)
  * [15] Zhou, S.K.: Discriminative anatomy detection: Classification vs regression. Pattern Recognition Letters 43, 25–38 (Jul 2014)


# Emojich – zero-shot emoji generation using Russian language: a technical
report

Alex Shonenkov  Sber AI, MIPT
<EMAIL_ADDRESS>
Kaggle: @shonenkov Daria Bakshandaeva  Sber AI
<EMAIL_ADDRESS>Denis Dimitrov  Sber AI, Lomonosov MSU
<EMAIL_ADDRESS>Aleksandr Nikolich  Sber AI, MIREA
<EMAIL_ADDRESS>
###### Abstract

This technical report presents a text-to-image neural network “Emojich” that
generates emojis using captions in Russian language as a condition. We aim to
keep the generalization ability of a pretrained big model ruDALL-E Malevich
(XL) 1.3B parameters at the fine-tuning stage, while giving special style to
the images generated. Here are presented some engineering methods, code
realization, all hyper-parameters for reproducing results and a Telegram bot
where everyone can create their own customized sets of stickers. Also, some
newly generated emojis obtained by "Emojich" model are demonstrated.

###### Index Terms:

text-to-image, emoji, deep learning, ruDALL-E

Figure 1:  Emojis generated by the text condition “женщина-кошка” (“catwoman”)

##  I Introduction

The transformer models which are normally pretrained on a large amount of
data, have proved their ability to cope successfully with the various
downstream tasks or adapt to new data related to the specific domain – and
this is achieved through fine-tuning. Examples of this approach are abundant
in the fields of Natural Language Processing [1], [2], [3] and Computer Vision
[4], [5]. However, multimodal models are currently at the cutting edge of ML
research, with text-to-image pretrained transformer models [6], [7], [8] being
one of the brightest examples in the field. As for improving the fine-tuning
process of such models, there is still considerable latitude for the
experiments.

It is rather time-consuming and challenging
procedure111https://unicode.org/emoji/proposals.html – to prepare and submit a
proposal for a new emoji to the Unicode Emoji Subcommittee; most importantly,
the success is not guaranteed. Emojis – with its expressiveness, universality
and ease of use – has infiltrated into our everyday digital communication. It
would be a great option, to generate unique and customize emojis on the fly,
especially since some messengers (such as Telegram) allow users to create
their own sets of icons. In this regard, recently introduced text-to-image
models which compute joint distribution over texts and images and generate the
latter by the former, seem very appealing. Similar efforts have already been
undertaken in [9], however, some limitations can be observed there: the
proposed approach is based on DC-GANs and word2vec embeddings, whereas the
transformer architecture of the recent models provides high-quality
representations which depend on the context and capture the meaning much
better (for instance, in [9] the samples generated on more than 1 word
embedding or some new unexpected text prompts were very noisy), and allows for
more deep interaction between modalities; the data used for training is rather
poor and restricted to 82 emotive faces; the resulted model cannot synthesize
new emojis (and the best prospect for it, as seen by the authors, is to
generate icons which are the combination of the existing ones). In view of the
above, we would like to fine-tune ruDALL-E model in order to test its ability
to generate emojis based on the textual descriptions – just like an artist
doing commissions to delight the customers.

##  II Dataset

The proposed Emoji dataset is collected by web scrapping: emoji icons with the
corresponding text captions in Russian are retrieved. The emoji pictures that
are naturally in RGBA format with the last channel (alpha) being an opacity
channel, are converted to RGB: pixels with opacity value less than 128 are
assigned white color code. Small emoji pictures are scaled to 256 px using
super-resolution approach Real-ESRGAN [10], that has been trained by Sber AI
with “$\times$4” scaling [11].

The full version of the dataset is available on
Kaggle222https://www.kaggle.com/shonenkov/russian-emoji. The dataset contains
2749 images and 1611 unique texts. Such mismatch is due to the following
reasons: there are sets, within which emojis differ only in color (for
instance, images of hands with different skin tones); some elements are
homonyms in Russian (for example, the descriptions for the images of a
medieval castle and a padlock are identical – “замок”). The length of text
descriptions varies from 1 to 7 words (about 67% of all samples are one- or
two-word descriptions).

Figure 2:  Distribution of word count values per description in the Emoji
dataset

##  III Fine-Tuning

The main goal of fine-tuning is to keep the “knowledge of the world” of
ruDALL-E Malevich (XL) model while adjusting the style of generated images to
emoji’s. ruDALL-E Malevich is a big multimodal pretrained transformer, which
learns the correlations between images and texts [8]. The freezing of the
feedforward and self-attention layers in a pretrained transformer has
demonstrated high performance in a multimodal setup [12], [13]. Thus, by
freezing our model we will definitely avoid catastrophic forgetting, increase
the efficiency of the process and reduce GPU memory usage.

The proposed Emoji dataset has limited variations of captions (see chapter II
for more details), therefore the model has all chances to be overfitted on the
text modality and lost generalization. To deal with this issue, the
coefficient of the weighted cross-entropy loss is increased to $10^{3}$ for
image representations (the codebook vectors). No data augmentations are used.

8-bit Adam [14] is used for optimization. This realization reduces the amount
of GPU memory needed for gradient statistics and provides more stable training
with fp16 precision. One cycle learning rate is chosen as a scheduler with the
following parameters: start lr 4e-7, max lr 1e-5, final lr 2e-8, warmup 0.1,
epochs 40, batch size 2, gradient clipping 1.0. Training time is 5h 30m using
1xA100.

The source code used for fine-tuning is available on
Kaggle333https://www.kaggle.com/shonenkov/emojich-rudall-e.

(a) Training loss

(b) Learning rate

Figure 3: Some measurements during fine-tuning.

##  IV Evaluation

A regular evaluation is an essential part of the fine-tuning process (this
holds true, without a doubt, for pretraining as well) as it indicates when the
fine-tuning should be stopped. In case of image generation, the most popular
metrics is FID [15] which is used to evaluate the quality of Generative
Adversarial Networks (GANs) performance. After obtaining the representations
for both sets of artificial and real images via the Inception Net, two
multivariate Gaussians fitted to these sets of feature embeddings are compared
by computing Fréchet distance between them. It is rightly noted [7] that this
metrics is suited for evaluation of general-domain unconditional generation
from simple distributions, thereby it is not the best option in our case.

In [7] another metric is proposed – Caption Loss. It involves fine-tuning the
model for the inverse task – image captioning – and further self-reranking
using cross-entropy values for the text tokens. This metric is worth
considering and will be used in further experiments.

In the current experiments, human evaluation is used: every 6 thousandths
iterations of fine-tuning, 64 images generated by the model are assessed using
such criteria as the degree of generality and abstraction, conformity to the
emoji aesthetics and overall quality of the image (for instance, smoothness
and absence of glitches/artefacts). Figure 4 demonstrates generated image
samples obtained by the model after every 2 thous. iterations of fine-tuning:
starting with the original ruDALL-E Malevich (XL) (in the upper left corner)
and finishing with the model that has been fine-tuning for 68 thous.
iterations in total (in the lower right corner). It can be observed that
initially images are realistic photos that do not correspond to the emoji
style; later they are modified and resemble drawings; after about 12 thous.
iterations images start to look like emojis more and more (although there
could be some features or artefacts that are out of style – a pose, for
example) while maintaining the recognizable traits of Einstein; after about 56
thous. iterations, however, the model is consistently loosing the “knowledge
of the world”: the images are becoming uniform and impersonal – Einstein is
transforming to an unknown man with a moustache, the standard emojis are
starting to prevail in the generation results.

Figure 4:  From the top left corner to the lower right corner: images
generated by the model after every 2 thous. iterations of fine-tuning using
the text prompt “Эйнштейн улыбается” (“Einstein is smiling”)

##  V Emoji generation

The emoji generation starts with a text prompt that describes the desired
emoji content. When the tokenized text is fed to Emojich, the model generates
the remaining codebook vectors auto-regressively. Every codebook vector is
selected item-by-item from a predicted multinomial probability distribution
over the image latents using nucleus top-p and top-k sampling with a
temperature [16] as a decoding strategy. The image is rendered from the
generated sequence of latent vectors by the decoder of the dVAE, which is
pretrained VQ-GAN [17] with Gumbel Softmax Relaxation [18]. Also, the decoder
is modified with the inverse discrete wavelet transform (IDWT) used in the
neural network MobileStyleGAN [19]; it allows restoring 512$\times$512
(instead of 256$\times$256) images almost without loss of quality. The authors
would like to thank @bes-dev for his help with the implementation of this
modification444https://github.com/bes-dev/vqvae_dwt_distiller.pytorch.

##  VI Emoji segmentation

In order to use images generated by Emojich as emoji icons or stickers in
messengers, they should be converted to RGBA format. However, the problem is
not as straightforward as assigning alpha channel’s value to 0 to all white
colored pixels: some inner parts of the image can be white and should not be
made transparent. Thus, the problem of image segmentation arises.

U-Net [ronneberger2015unet] with EfficientNetB7 as an encoder is used as a
binary semantic segmentation model (with 0 meaning complete transparency and 1
– complete opacity). The training RGBA dataset is obtained using pseudo-
labeling method: at first, U-Net model is trained on the initial dataset of
emojis in RGBA format (2749 pictures); then predictions on the emojis
generated by Emojich are made by the model – the predicted segmented images,
which confidence value is not less than 0.99, are added to the training data;
the process repeats until the training reaches the plateau. Some nontrivial
cases are segmented manually using classical contour-based approach
555https://docs.opencv.org/3.4/d4/d73/tutorial_py_contours_begin.html and
further are added to the training set as well. The size of the final train
dataset is 246089 images. All images of the validation set (143 icons) are
segmented manually.

The resulting pipeline involves two possible regimes: the generated image is
segmented by the trained U-Net model; if the confidence value is less than the
threshold (0.99), classical contour-based approach is used.

##  VII Results

In the appendix, some emoji pictures created through the proposed methods are
demonstrated. All examples are generated automatically (without manual cherry-
picking) with the following hyper-parameters: seed 42, batch size 16, top-k
2048, top-p 0.995, temperature 1.0, GPU A100. To obtain emojis of better
quality we advise to use more attempts ($\sim 512$) and select the best one
manually. Remember, for the great art makers creating just one masterpiece is
enough to become “great”.

Moreover, we propose a segmentation procedure based on U-Net to crop the
background of the generated images of the emojis. It is necessary to create
looking good stickers. Thus everyone can generate their own customized sets of
stickers using this Telegram bot: https://t.me/rudalle_emojich_bot.

## Acknowledgment

The authors would like to thank Sber AI, SberDevices and SberCloud for
granting the GPU-resources for the experiments.

## References

  * [1] D. Grießhaber, J. Maucher, and N. T. Vu, “Fine-tuning BERT for low-resource natural language understanding via active learning,” in _Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain (Online), December 8-13, 2020_ , D. Scott, N. Bel, and C. Zong, Eds. International Committee on Computational Linguistics, 2020, pp. 1158–1171. [Online]. Available: https://doi.org/10.18653/v1/2020.coling-main.100
  * [2] E. B. Zaken, S. Ravfogel, and Y. Goldberg, “Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models,” _CoRR_ , vol. abs/2106.10199, 2021. [Online]. Available: https://arxiv.org/abs/2106.10199
  * [3] M. Mosbach, M. Andriushchenko, and D. Klakow, “On the stability of fine-tuning BERT: misconceptions, explanations, and strong baselines,” in _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/forum?id=nzpLWnVAyah
  * [4] O. Kara, A. Sehanobish, and H. H. Corzo, “Fine-tuning vision transformers for the prediction of state variables in ising models,” _CoRR_ , vol. abs/2109.13925, 2021. [Online]. Available: https://arxiv.org/abs/2109.13925
  * [5] D. Malpure, O. Litake, and R. Ingle, “Investigating transfer learning capabilities of vision transformers and cnns by fine-tuning a single trainable block,” _CoRR_ , vol. abs/2110.05270, 2021. [Online]. Available: https://arxiv.org/abs/2110.05270
  * [6] A. Ramesh, M. Pavlov, G. Goh, S. Gray, C. Voss, A. Radford, M. Chen, and I. Sutskever, “Zero-shot text-to-image generation,” in _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 2021, pp. 8821–8831. [Online]. Available: http://proceedings.mlr.press/v139/ramesh21a.html
  * [7] M. Ding, Z. Yang, W. Hong, W. Zheng, C. Zhou, D. Yin, J. Lin, X. Zou, Z. Shao, H. Yang, and J. Tang, “Cogview: Mastering text-to-image generation via transformers,” _CoRR_ , vol. abs/2105.13290, 2021. [Online]. Available: https://arxiv.org/abs/2105.13290
  * [8] A. Shonenkov, “Github ruDALL-E models by SberAI,” 2021, accessed: 02-11-2021. [Online]. Available: https://github.com/sberbank-ai/ru-dalle
  * [9] D. Radpour and V. Bheda, “Conditional generative adversarial networks for emoji synthesis with word embedding manipulation,” _CoRR_ , vol. abs/1712.04421, 2017. [Online]. Available: http://arxiv.org/abs/1712.04421
  * [10] X. Wang, L. Xie, C. Dong, and Y. Shan, “Real-esrgan: Training real-world blind super-resolution with pure synthetic data,” 2021.
  * [11] I. Pavlov, “Github Real-ESRGAN with trained models by SberAI,” 2021, accessed: 02-11-2021. [Online]. Available: https://github.com/sberbank-ai/Real-ESRGAN
  * [12] K. Lu, A. Grover, P. Abbeel, and I. Mordatch, “Pretrained transformers as universal computation engines,” 2021.
  * [13] D. Bakshandaeva, D. Dimitrov, A. Shonenkov, M. Potanin, V. Arkhipkin, D. Karachev, V. Davydova, A. Voronov, M. Martynov, N. Semenova, M. Stepnov, E. Tutubalina, A. Chertok, and A. Petiushko, “Many heads but one brain: an overview of Fusion Brain Challenge on AI Journey 2021,” 2021.
  * [14] T. Dettmers, M. Lewis, S. Shleifer, and L. Zettlemoyer, “8-bit optimizers via block-wise quantization,” 2021.
  * [15] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” in _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, Eds., 2017, pp. 6626–6637. [Online]. Available: https://proceedings.neurips.cc/paper/2017/hash/8a1d694707eb0fefe65871369074926d-Abstract.html
  * [16] A. Holtzman, J. Buys, M. Forbes, and Y. Choi, “The curious case of neural text degeneration,” _CoRR_ , vol. abs/1904.09751, 2019. [Online]. Available: http://arxiv.org/abs/1904.09751
  * [17] P. Esser, R. Rombach, and B. Ommer, “Taming transformers for high-resolution image synthesis,” 2020.
  * [18] M. J. Kusner and J. M. Hernández-Lobato, “Gans for sequences of discrete elements with the gumbel-softmax distribution,” 2016.
  * [19] S. Belousov, “Mobilestylegan: A lightweight convolutional neural network for high-fidelity image synthesis,” _CoRR_ , vol. abs/2104.04767, 2021. [Online]. Available: https://arxiv.org/abs/2104.04767

(a) "зима в горах" ("a winter in the mountains")

(b) "флаг зомби апокалипсиса" ("a zombie apocalypse flag")

(c) "флаг Cбербанка" ("Sberbank flag")

(d) "храм Василия Блаженного" ("St. Basil’s Cathedral")

(e) "вишневая девятка" ("cherry-colored Lada 2109")

(f) "Дональд Трамп из лего" ("Donald Trump made of LEGO")

(g) "человек ест яблоко" ("a human eats an apple")

(h) "ежик в голубой шапке" ("a hedgehog in a blue hat")

(i) "волк в овечьей шкуре" ("a wolf in sheep’s clothing")

(j) "кролик синего цвета" ("a blue rabbit")

(k) "розовая альпака улыбается" ("pink alpaca is smiling")

(l) "арфа в форме улитки" ("a snail-shaped harp")


# Competency Problems:
On Finding and Removing Artifacts in Language Data

Matt Gardner*♠ William Merrill*♠ Jesse Dodge♠
Matthew E. Peters♠ Alexis Ross♠ Sameer Singh♡ Noah Smith♣♠
♠Allen Institute for Artificial Intelligence
♡University of California, Irvine
♣University of Washington
<EMAIL_ADDRESS>Equal contribution

###### Abstract

Much recent work in NLP has documented dataset artifacts, bias, and spurious
correlations between input features and output labels. However, how to tell
which features have “spurious” instead of legitimate correlations is typically
left unspecified. In this work we argue that for complex language
understanding tasks, _all_ simple feature correlations are spurious, and we
formalize this notion into a class of problems which we call _competency
problems_. For example, the word “amazing” on its own should not give
information about a sentiment label independent of the context in which it
appears, which could include negation, metaphor, sarcasm, etc. We
theoretically analyze the difficulty of creating data for competency problems
when human bias is taken into account, showing that realistic datasets will
increasingly deviate from competency problems as dataset size increases. This
analysis gives us a simple statistical test for dataset artifacts, which we
use to show more subtle biases than were described in prior work, including
demonstrating that models are inappropriately affected by these less extreme
biases. Our theoretical treatment of this problem also allows us to analyze
proposed solutions, such as making local edits to dataset instances, and to
give recommendations for future data collection and model design efforts that
target competency problems.

##  1 Introduction

Attempts by the natural language processing community to get machines to
understand language or read text are often stymied in part by issues in our
datasets (Chen et al., 2016; Sugawara et al., 2018). Many recent papers have
shown that popular datasets are prone to shortcuts, dataset artifacts, bias,
and spurious correlations (Jia and Liang, 2017; Rudinger et al., 2018; Costa-
jussà et al., 2019). While these empirical demonstrations of deficiencies in
the data are useful, they often leave unspecified fundamental questions of
what exactly is a “spurious” correlation, instead of a feature that is
legitimately predictive of some target label.

In this work we attempt to address this question theoretically. We begin with
the assumption that in a language understanding problem, no single feature on
its own should contain information about the class label. That is, _all_
simple correlations between input features and output labels are spurious:
$p(y|x_{i})$, for any feature $x_{i}$, should be uniform over the class label.
We call the class of problems that meet this assumption _competency
problems_.111Our use of the term “competency problems” is inspired by, but not
identical to, the term “competence” in linguistics. We do not take a position
on competence vs. performance in linguistics, and are simply referring to the
notion that humans can understand essentially any well-formed utterance in
their native language.

Figure 1: A statistical test for deviation from a competency problem, where no
individual feature (here word types) should give information about the class
label. All features above the blue line have detectable correlation with class
labels, using a very conservative Bonferroni-corrected statistical test.

This assumption places a very strong restriction on the problems being
studied, but we argue that it is a reasonable description of complex language
understanding problems. Consider, for example, the problem of sentiment
analysis on movie reviews. A single feature might be the presence of the word
_“amazing”_ , which could be legitimately correlated with positive sentiment
in some randomly-sampled collection of actual movie reviews. However, that
correlation tells us more about word frequency in movie reviews than it tells
us about a machine’s ability to understand the complexities of natural
language. A competent speaker of a natural language would know that
_“amazing”_ can appear in many contexts that do not have positive sentiment
and would not base their prediction on the presence of this feature alone.
That is, the information about the sentiment of a review, and indeed the
_meaning_ of natural language, is contained in complex feature interactions,
not in isolated features. To evaluate a machine’s understanding of language,
we must remove all simple feature correlations that would allow the machine to
predict the correct label without considering how those features interact.

Collecting data that accurately reflects the assumptions of a competency
problem is very challenging, especially when humans are involved in creating
it. Humans suffer from many different kinds of bias and priming effects, which
we collectively model in this work with rejection sampling during data
collection. We theoretically analyze data collection under this biased
sampling process, showing that any amount of bias will result in increasing
probability of statistically-significant spurious feature correlations as
dataset size increases.

This theoretical treatment of bias in data collection gives us a new, simple
measure of data artifacts, which we use to explore artifacts in several
existing datasets. Figure 1 revisits prior analyses on the SNLI dataset Bowman
et al. (2015) with our statistical test. An analysis based on pointwise mutual
information (e.g., Gururangan et al., 2018) would correspond to a horizontal
line in that figure, missing many features that have less extreme but still
significant correlations with class labels. These less extreme correlations
still lead models to overweight simple features. The problem of bias in data
collection is pervasive and not easily addressed with current learning
techniques.

Our framework also allows us to examine the theoretical impact of proposed
techniques to mitigate the bias. We focus primarily on performing local edits
after data collection, deriving properties of any local edit procedure that
must hold in order for the procedure to effectively remove data artifacts.
These proofs give dataset builders tools for monitoring the data collection
process to be sure that resultant datasets are as artifact-free as possible.
Our analysis of local edits additionally suggests a strong relationship to the
idea of _sensitivity_ in boolean functions, and we identify gaps in the theory
of sensitivity that need to be filled to properly account for bias in sampled
datasets.

We conclude with a few simple recommendations for future data collection
efforts based on this analysis, including: (1) find ways to inject randomness
into data collection processes, to mitigate priming effects; and (2) consider
using local perturbation methods to augment data collection, preferably doing
this _after_ data has been split into training and test sets, using
_different_ perturbation processes between train and test. We believe that our
theoretical analysis of these problems provides a good starting point for
future analyses of methods to improve data collection processes in NLP, as
well as insights for inductive biases that could be introduced to better model
competency problems.

##  2 Competency Problems

We define a _competency problem_ to be one where the marginal distribution
over labels given any single feature is uniform. For our analysis, we restrict
ourselves to the class of boolean functions: we assume an input vector
$\mathbf{x}$ and an output value $y$, where $\mathbf{x}\in\\{0,1\\}^{d}$ and
$y\in\\{0,1\\}$.222Boolean functions are quite general, and many machine
learning problems can be framed this way. For NLP, consider that before the
rise of embedding methods, language was often represented in machine learning
models as bags of features in a very high-dimensional feature space, exactly
as we are modeling the problem here. The first (embedding) layer of a modern
transformer is still very similar to this, with the addition of a position
encoding. The choice of what counts as a “simple feature” is admittedly
somewhat arbitrary; we believe that considering word types as simple features,
as we do in most of our analysis, is uncontroversial, but there are other more
complex features which one still might want to control for in competency
problems. In formal terms, our assumption in this setting is that
$p(y|x_{i})=0.5$ for all $i$. In other words, the information mapping the
inputs to the label is found in complex feature interactions, not in
individual features.

Our core claim is that language understanding requires composing together many
pieces of meaning, each of which on their own are largely uninformative about
the meaning of the whole. We do not believe this claim is controversial or
new, but its implications for posing language understanding as a machine
learning problem are under-appreciated and somewhat counter-intuitive. If a
model picks up on individual feature correlations in a dataset, it has learned
something _extra-linguistic_ , such as information about human biases, not
about how words come together to form meaning, which is the heart of natural
language understanding. To push machines towards linguistic competence, we
must control for all sources of extra-linguistic information, ensuring that no
simple features contain information about class labels.

For some language understanding problems, such as natural language inference,
this intuition is already widely held. We find it surprising and problematic
when the presence of the word _“cat”_ , _“sleeping”_ or even _“not”_ in either
the premise or the hypothesis gives a strong signal about an entailment
decision (Gururangan et al., 2018; Poliak et al., 2018). Competency problems
are broader than this, however. Consider the case of sentiment analysis. It is
true that a movie review containing the word _“amazing”_ is more likely than
not to express positive sentiment about the movie. This is because of
distributional effects in how humans choose to use phrases in movie reviews.
If our goal is to build a system that can accurately classify the sentiment of
movie reviews, this is a useful feature. But if our goal is instead to get a
machine that understands how sentiment is expressed in language, this feature
is a red herring that must be controlled for to truly test linguistic
competence.

##  3 Biased Sampling

To get machines to perform well on competency problems, we need data that
accurately reflects the competency assumption, both to evaluate systems and
(presumably) to train them. However, humans suffer from blind spots, social
bias, priming, exhaustion, and numerous other psychological effects that make
collecting data for competency problems incredibly challenging. Real examples
of these effects include instructions in a crowdsourcing task that prime
workers to use particular language when producing examples,333This is
ubiquitous in crowdsourcing; see, e.g., common patterns in DROP (Dua et al.,
2019) or ROPES (Lin et al., 2019) that ultimately derive from annotator
instructions. or distributional effects in source material, such as the
_“amazing”_ examples earlier, or racial bias in face recognition (Buolamwini
and Gebru, 2018) and abusive language detection datasets (Davidson et al.,
2019).

In order to formally analyze the impact of human bias on collecting data for
competency problems, we need a plausible model of this bias. We represent this
bias as rejection sampling from the target competency distribution based on
single feature values. Specifically, we assume the following dataset
collection procedure. First, a person samples an instance from an unbiased
distribution $p_{u}(\mathbf{x},y)$ where the competency assumption holds. The
person examines this instance, and if feature $x_{i}=1$ appears with label
$y=0$, the person rejects the instance and samples a new instance, with
probability $r_{i}$. If $y=0$ corresponds to negative sentiment and $x_{i}$ is
the word _“amazing”_ , a high value for $r_{i}$ would lead to _“amazing”_
appearing more often with positive sentiment, as is observed in typical
sentiment analysis datasets.

We do not claim that rejection sampling is a plausible psychological model of
the process of dataset construction. However, we _do_ think it is a reasonable
approximation of the _outcome_ of human bias on data creation, for a broad
class of biases that have empirically been found in existing datasets, and it
is relatively easy to analyze. Additionally, rejection sampling based on
single features alone is overly simplistic, but the dynamics of spurious
correlations that we derive will still be applicable if the rejection sampling
is done on more complex feature interactions.

###  3.1 Emergence of Artifacts Under Rejection Sampling

Let $p_{u}(y|x_{i})$ be the conditional probability of $y=1$ given $x_{i}=1$
under the unbiased distribution, $p_{b}(y|x_{i})$ be the same probability
under the biased distribution, and $\hat{p}(y|x_{i})$ denote the empirical
probability that $y=1$ given $x_{i}=1$ within a biased dataset of $n$ samples.
Additionally, let $f_{i}$ be the marginal probability $p_{u}(x_{i})$. Recall
that $p_{u}(y|x_{i})$ is $0.5$ by assumption in competency problems.

We will say that dimension $i$ has an _artifact_ if the empirical probability
$\hat{p}(y|x_{i})$ statistically differs from $0.5$. In this section, we will
show that an artifact emerges if there is a bias at dimension $i$ in the
sampling procedure, which is inevitable for some features in practice. We will
formalize this bias in terms of a rejection sampling probability $r_{i}$.

For a single sample $\mathbf{x},y$, we first derive the joint and marginal
probabilities $p_{b}(y,x_{i})$ and $p_{b}(x_{i})$, from which we can obtain
$p_{b}(y|x_{i})$. These formulas use a recurrence relation obtained from the
rejection sampling procedure.

$\displaystyle p_{b}(y,x_{i})$
$\displaystyle=\frac{1}{2}f_{i}+\frac{1}{2}f_{i}r_{i}p_{b}(y,x_{i})$
$\displaystyle\therefore p_{b}(y,x_{i})$
$\displaystyle=\frac{f_{i}}{2-f_{i}r_{i}}$ $\displaystyle p_{b}(x_{i})$
$\displaystyle=\frac{1}{2}f_{i}+\frac{1}{2}f_{i}(1-r_{i})+\frac{1}{2}f_{i}r_{i}p_{b}(x_{i})$
$\displaystyle\therefore p_{b}(x_{i})$
$\displaystyle=\frac{2f_{i}-f_{i}r_{i}}{2-f_{i}r_{i}}$ $\displaystyle
p_{b}(y\mid x_{i})$ $\displaystyle=\frac{p_{b}(y,x_{i})}{p_{b}(x_{i})}$
$\displaystyle\therefore p_{b}(y\mid x_{i})$ $\displaystyle=\frac{1}{2-r_{i}}$

With no bias ($r_{i}=0$), this probability is $0.5$, as expected, and it rises
to $1$ as $r_{i}$ increases to $1$.

We define $\hat{p}(y|x_{i})$ as the empirical expectation of $p_{b}(y|x_{i})$
over $n$ samples containing $x_{i}$, with different samples indexed by
superscript $j$. We can represent $\hat{p}(y|x_{i})$ as

$\displaystyle\hat{p}(y\mid x_{i})=\frac{1}{n}\sum_{j=1}^{n}y^{j}.$

Note that $\hat{p}$ is a conditional binomial random variable. By the central
limit theorem, $q$ is approximately
$\sim\mathcal{N}(\mu_{\hat{p}},\sigma_{\hat{p}}^{2})$ for large $n$, where

$\displaystyle\mu_{\hat{p}}$ $\displaystyle=p_{b}(y\mid
x_{i})=\frac{1}{2-r_{i}}$ $\displaystyle\sigma_{\hat{p}}^{2}$
$\displaystyle=\left(\frac{1-r_{i}}{(2-r_{i})^{2}}\right)^{2}\cdot\frac{1}{n}.$

This variance is inversely proportional to the number of samples $n$. Thus,
$\hat{p}(y|x_{i})$ can be well approximated by its expected value for a large
number of samples. As the rejection probability $r_{i}$ increases, the center
of this distribution tends from $0.5$ to $1$. This formalizes the idea that
bias in the sampling procedure will cause the empirical probability
$\hat{p}(y|x_{i})$ to deviate from $0.5$, even if the “true” probability is
$0.5$ by assumption. Increasing the sample size $n$ concentrates the
distribution inversely proportional to $\sqrt{n}$, but the expected value is
unchanged. Thus, artifacts created by rejection sampling will not be combated
by simply sampling more data from the same biased procedure—the empirical
probability will still be biased by $r_{i}$ even if $n$ increases arbitrarily.
These persistent artifacts can be exploited at _i.i.d._ test time to achieve
high performance, but will necessarily fail if the learner is evaluated under
the competency setting.

###  3.2 Hypothesis Test

Here we set up a hypothesis test to evaluate if there is enough evidence to
reject the hypothesis that $r_{i}$ is 0, i.e., that the data is unbiased. In
this case, we can use a one-sided binomial proportion hypothesis test, as our
rejection sampling can only lead to binomial proportions for $p_{b}(y\mid
x_{i})$ that are greater than $\frac{1}{2}$. Our null hypothesis is that the
binomial proportion $p_{b}(y\mid x_{i})=0.5=p_{0}$, or equivalently, that
$r_{i}=0$. Our alternative hypothesis is that $p_{b}(y\mid x_{i})\geq 0.5$.
Let $\hat{p}$ be the observed probability. We can compute a
$z$-statistic,444The use of a $z$-statistic depends on the normal
approximation to a binomial distribution, which holds for large $n$. using the
standard formula:

$\displaystyle z^{*}=\frac{\hat{p}-p_{0}}{\sqrt{p_{0}(1-p_{0})/n}}$ (1)

Thus, if our observed proportion $\hat{p}$ is far from $p_{0}=0.5$, we will
have enough evidence to reject the null hypothesis that $r_{i}=0$. This
depends on $n$ as well, and to explore this interaction, we can solve for
$\hat{p}$:

$\displaystyle\hat{p}=\frac{z^{*}}{2\sqrt{n}}+\frac{1}{2}$

for a given value of $n$ and confidence level $z^{*}$.

##  4 Empirical Analysis

With a hypothesis test in hand we can examine existing datasets for evidence
of statistically-significant feature bias, and then explore the extent to
which this bias impacts models supervised with this data. Prior work has used
pointwise mutual information (PMI) to find features that have high correlation
with labels (e.g., Gururangan et al., 2018). This measure is useful for
understanding why certain features might get used as deterministic decision
rules by models (Ribeiro et al., 2018; Wallace et al., 2019). However, studies
involving PMI have also intuitively understood that PMI by itself does not
tell the whole story, as a strict ranking by PMI would return features that
only appear once in the dataset. To account for this problem, they used
arbitrary cutoffs and included information about feature occurrence in
addition to their PMI ranking. A benefit of our approach to defining and
detecting artifacts is that we have a single statistical test that takes into
account both the number of times a feature appears and how correlated it is
with a single label. We use this test to find features with the strongest
statistical evidence for artifacts (§4.1) and then show empirically that
models use these features inappropriately when making predictions (§4.2). This
analysis goes beyond deterministic prediction rules, showing that the impact
of sampling bias on model behavior is subtle and pervasive.

###  4.1 Data Analysis

Here we analyze the Stanford Natural Language Inference dataset (SNLI; Bowman
et al., 2015) with the hypothesis test laid out in Section 3.2. We compute a
$z$-statistic for every word that appears in the data,555We remove punctuation
and split text into tokens on whitespace only. counting each appearance in an
instance as a separate occurrence for the purposes of computing $n$ and
$\hat{p}$ in Equation 1. We then plot the $z$-statistic for each token against
the number of times the token appears in the data. We additionally plot a
curve for the value of the $z$-statistic for which the null hypothesis (that
$r_{i}=0$) should be rejected, using a significance level of $\alpha=0.01$ and
a conservative Bonferroni correction Bonferroni (1936) for all 28,000
vocabulary items. This analysis is shown in Figure 1.

We find a very large number of deviations from the competency assumption, many
more than would be suggested by a PMI-based analysis. PMI equals
$\log\frac{\hat{p}(y|x_{i})}{\hat{p}(y)}$; because $\hat{p}(y)$ does not vary
across features, and the data is balanced over labels, a PMI analysis ranks
features by $\hat{p}(y|x_{i})$, looking only at the $y$-axis in Figure 1.666In
practice an arbitrary threshold is chosen on the $x$-axis to avoid rare
features. Again here a statistical test is a more principled way to account
for rare features. But the threshold for which a deviation in
$\hat{p}(y|x_{i})$ becomes a statistical artifact depends on the number of
times the feature is seen, so our statistical test gives a simpler and more
complete picture of data artifacts. Strong statistical deviations with less
extreme PMI values still impact model behavior, as demonstrated in the
following section and in Section 6.

###  4.2 Model Analysis

The previous section illustrates a large number of individual token dataset
artifacts in the SNLI dataset. Here, we ask whether typical NLP models learn
to bias their predictions based on these artifacts for both the SNLI and RTE
Dagan et al. (2005)777We use the RTE data distributed with SuperGlue Wang et
al. (2019). datasets. Importantly, this analysis focuses on words with high
$z$-statistics. This includes words such as _“for”_ and _“to”_ (the two words
with highest $z$-statistic for the neutral class), and _“there”_ and _“near”_
(the highest and fifth-highest $z$-statistic for the entailment class).

To measure the model bias learned from these words, we employ RoBERTa-base Liu
et al. (2019) fine-tuned on RTE, and ALBERT-base Lan et al. (2020) fine-tuned
on SNLI.888Both models are from Morris et al. (2020), and implemented in
Transformers Wolf et al. (2020). Given a single type such as
$x_{i}=$_“nobody”_ and a target class such as $y=$“contradiction”, we estimate
the model $\tilde{p}(y|x_{i})$ as follows. We first create two synthetic input
examples, one with the premise containing only the single token with an empty
hypothesis, and one with an empty premise and hypothesis containing the single
token. As each input contains only a single token without additional context,
this tests whether the model will bias its output based on the token. We run a
forward pass with each input and average the target class probabilities as an
estimate of $\tilde{p}(y|x_{i})$. All of the word types in each dataset
appearing at least 20 times999The minimum count at which the normal
approximation to binomial is reliable. are partitioned among the classes based
on their largest class conditional $z^{*}$, and for each class we form two
cohorts of 50 tokens each with the highest and lowest $z^{*}$. Let
$\mathcal{X}_{y,z^{*}_{<}}$ denote the set of $x_{i}$ with the lowest $z^{*}$
for class $y$ and similarly let $\mathcal{X}_{y,z^{*}_{>}}$ denote the set
with the largest $z^{*}$. Finally, we compute the average
$\Delta\tilde{p}_{y}=\sum_{x_{i}\in\mathcal{X}_{y,z^{*}_{>}}}\tilde{p}(y|x_{i})-\sum_{x_{i}\in\mathcal{X}_{y,z^{*}_{<}}}\tilde{p}(y|x_{i})$.

The results are shown in Table 1. As can be seen, these models exhibit
significant bias based on these single token inputs, with
$\Delta\tilde{p}_{y}$ exceeding 10% for some classes. The bias is much more
extreme for SNLI versus RTE, likely due to the fact that RTE has two orders of
magnitude less data than SNLI.

Dataset | Class | $\Delta\hat{p}_{y}$
---|---|---
RTE | entailment | +2.2 %
SNLI | entailment | +14.7 %
SNLI | neutral | +7.9 %
SNLI | contradiction | +12.5 %
Table 1: Comparison of the average model predicted class probability for a
single token across two cohorts of large $z^{*}$ tokens and low $z^{*}$ tokens
using RoBERTa (RTE) and ALBERT (SNLI).

##  5 Mitigating Artifacts with Local Edits

Many works have tried to remove data artifacts by making minimal changes to
existing data (Shekhar et al., 2017; Sennrich, 2017; Zhao et al., 2018, _inter
alia_). In this section we show that this kind of data augmentation can be
effective with an appropriately sensitive edit model, where _sensitivity_
refers to how often a change to inputs results in the label changing. However,
because humans are again involved in making these changes, achieving
appropriate sensitivity is challenging, and bias in this process can lead to
the introduction of new artifacts. This suggests that care must be taken when
doing edit-based data augmentation, as large edited training datasets are not
likely to be artifact-free (cf. Tafjord et al., 2019; Huang et al., 2020).

Imagine a new dataset $\mathcal{D}_{e}$ consisting of samples
$\mathbf{x}^{\prime},y^{\prime}$ generated by making local edits according to
the following repeated procedure:

  1. 1.

Randomly sample an instance $\mathbf{x}$ from a dataset $\mathcal{D}_{b}$ of
$n$ instances created under the biased distribution $p_{b}$.

  2. 2.

Make some changes to $\mathbf{x}$ to arrive at $\mathbf{x^{\prime}}$.

  3. 3.

Manually label $y^{\prime}$ and add
$\langle\mathbf{x^{\prime}},y^{\prime}\rangle$ to $\mathcal{D}_{e}$.

We examine the expected probability $p_{e}(y^{\prime}|x^{\prime}_{i})$ under
this edit process. To derive this probability, we will need to know the
probability that a change to $\mathbf{x}$ changes $y$. We define the _edit
sensitivity_ $s$ to be this probability, i.e., $s=p_{b}(y^{\prime}=\neg y)$.
The other quantity of interest for an edit model is $e_{i}$, the probability
that dimension $i$ gets flipped when going from $\mathbf{x}$ to
$\mathbf{x^{\prime}}$. We develop theory relating these quantities to whether
or not samples generated by making local edits will be unbiased. The following
theorem (and corollaries) can be taken to show that $s$ and $e_{i}$ control
whether local edits will debias first-order artifacts.

######  Proposition 1.

Assume $r_{i}\neq 0$. Then,

$\frac{1+e_{i}}{s}=2\iff p_{e}(y^{\prime}\mid x^{\prime}_{i})=\frac{1}{2}.$

###### Proof.

First consider the case where $y^{\prime}=\neg y$. We marginalize the
probability as follows:

$\displaystyle p_{e}(y^{\prime}\mid x^{\prime}_{i})$ $\displaystyle=p_{b}(\neg
y\mid x_{i})(1-e_{i})+p_{b}(\neg y\mid\neg x_{i})e_{i}$
$\displaystyle=\frac{2-2r_{i}+r_{i}e_{i}}{2(2-r_{i})}.$

We now consider the other case where $y^{\prime}=y$.

$\displaystyle p_{e}(y^{\prime}\mid x^{\prime}_{i})$
$\displaystyle=p_{b}(y\mid x_{i})(1-e_{i})+p_{b}(y\mid\neg x_{i})e_{i}$
$\displaystyle=\frac{2-r_{i}e_{i}}{2(2-r_{i})}.$

Finally we marginalize over whether $y^{\prime}=\neg y$, an event which has
probability $s$.

$\displaystyle p_{e}(y^{\prime}\mid x^{\prime}_{i})$
$\displaystyle=\frac{(2-2r_{i}+r_{i}e_{i})s+(2-r_{i}e_{i})(1-s)}{2(2-r_{i})}$
$\displaystyle=\frac{2-(2s-e_{i})r_{i}}{2(2-r_{i})}.$

At this point, we solve for when $p_{e}(y^{\prime}|x^{\prime}_{i})=0.5$. Here
we use the assumption that $r_{i}\neq 0$.

$\displaystyle\frac{1}{2}$
$\displaystyle=\frac{2-(2s-e_{i})r_{i}}{2(2-r_{i})}$ $\displaystyle 2-r_{i}$
$\displaystyle=2-(2s-e_{i})r_{i}$ $\displaystyle r_{i}$
$\displaystyle=(2s-e_{i})r_{i}$ $\displaystyle\therefore s$
$\displaystyle=\frac{1+e_{i}}{2}.$

∎

This can be extended to show that

$\frac{1+e_{i}}{s}\leq 2\iff p_{e}(y^{\prime}\mid
x^{\prime}_{i})\leq\frac{1}{2},$

meaning local editing will dilute or cancel out artifacts from rejection
sampling if the edit sensitivity is high enough, but if it is too high, it can
introduce artifacts in the opposite direction. In practice, if it is possible
to pick a dimension to flip more or less uniformly, then $e_{i}\approx 0$ in a
high-dimensional space, so engineering $s\approx 0.5$ should produce artifact-
free additional samples with $p_{e}(y^{\prime}|x^{\prime}_{i})\approx 0.5$.
Also note that in practice the distribution we care about is
$\hat{p}(y^{\prime}|x^{\prime}_{i})$, not $p_{e}(y^{\prime}|x^{\prime}_{i})$.
However, with large enough $n$, this sampling distribution should concentrate
tightly around $p_{e}$.

Furthermore, edit sensitivity and edit dimension are actually empirically
measurable when constructing a dataset. Accepting the competency assumption,
this empirical measurement can actually give theoretical guarantees for the
degree to which the local editing will alleviate artifacts (i.e., this gives
us a principled way to decide between different edit models).

#### Biased Editing

A major challenge with implementing a properly-sensitive edit model is that
the probability of a label change needs to depend on the probability of a
feature being included in the edit. This seems very hard to accomplish for all
dimensions simultaneously, especially when humans make edits and have a biased
selection of which features to edit (increasing $e_{i}$ substantially for some
features), and because for most natural language problems more than one
feature must be edited at once in order to retain well-formed inputs. Local
edits, if done improperly, can just as easily introduce their own deviations
from the competency assumption about $p_{e}(y|x_{i})$. To demonstrate this, we
give two simple examples of edit procedures that fail to resolve bias or
introduce a new bias.

First, we construct a deterministic flipping procedure that looks at pairs of
features to decide what to flip. For some indices $i,j$, the procedure
implements the following conditional logic:

  1. 1.

If $x_{i}\wedge x_{j}$, then flip $x_{i}$.

  2. 2.

If $x_{i}\wedge\neg x_{j}$, then flip $x_{i}$.

  3. 3.

If $\neg x_{i}\wedge x_{j}$, then flip $x_{j}$.

  4. 4.

If $\neg x_{i}\wedge\neg x_{j}$, then flip $x_{i}$.

This augmentation procedure will _never_ produce samples satisfying
$x_{i}\wedge x_{j}=1$. Thus, $p_{e}(y|x_{i},x_{j})=p_{b}(y|x_{i},x_{j})$, no
matter how many local augmentations are made, and second-order feature
correlations will not be resolved.

Second, consider another deterministic flipping procedure which examines only
a single feature, but also includes the label:

  1. 1.

If $\neg x_{j}\wedge\neg y$, and flipping $x_{j}$ will flip $y$, then flip
$x_{j}$.

  2. 2.

If $x_{j}\wedge y$, and flipping $x_{j}$ will flip $y$, then flip $x_{j}$.

  3. 3.

Else flip some other dimension randomly.

This procedure will tend to introduce instances where $x_{j}$ is correlated
with $y$. The more flips are made, the more $p_{e}(y|x_{j})$ will deviate from
$0.5$.

These existence proofs use deterministic, adversarial perturbation functions;
more realistic assumptions would relax the determinism to get softer (but
still problematic) versions of the above arguments. We present these existence
proofs simply to encourage caution with the blanket application of local edits
to solve dataset artifacts.

###  5.1 Local Edits in BoolQ

We empirically investigate the effectiveness of local edits for reducing
single feature artifacts using locally edited samples generated from the
boolean questions dataset (BoolQ; Clark et al., 2019a). BoolQ consists of
pairs of paragraphs ($p$) and questions ($q$), where each $q$ has a binary
answer that can be found by reasoning over $p$. We define each feature $x_{i}$
as the occurrence of a particular token within $q$. This setup perfectly
reflects the assumptions underlying Proposition 1. Gardner et al. (2020)
generated additional BoolQ data by making local edits to the question text and
recording the updated binary label.

Figure 2 visualizes the effect of these changes on single-feature artifacts by
comparing the artifact statistics for original sentences from the development
set to the statistics for the edited sentences generated by Gardner et al.
(2020). Whereas some of the word types in the original data exhibit artifacts
in the positive ($>0.5$) direction, within the edited data, the majority of
types fall within the confidence region. Empirically, we find that the values
$(1+e_{i})/s$ tightly concentrate around a mean of $1.94$, which, by
Proposition 1, explains why most of the $\hat{p}(y|x_{i})$ values for the
edited samples are not significantly different from $0.5$. The mean
$\hat{p}(y|x_{i})$ for the edited samples is $0.47$. However, some features
have much lower $\hat{p}(y|x_{i})$ values; if much more data were constructed
with these same ratios, it is possible that artifacts could arise in the
opposite direction. This case study illustrates the value of leveraging our
theory (Proposition 1) to engineer better edit models. If the edit model is
designed to appropriately balance sensitivity and feature edit probability,
then it can be guaranteed that $p_{e}(y|x_{i})=0.5$, meaning that local
editing will not “overshoot” to create artifacts in the opposite direction
from the original data.

Figure 2: The artifact statistics of the original BoolQ samples are plotted in
red, compared to the artifact statistics over the edited instances, plotted in
green.

###  5.2 Local Edits and Boolean Sensitivity

In the above discussion we used the term _sensitivity_ in an informal way to
describe the probability that a local edit changes the label. This term also
has a related formal definition in the study of boolean functions, where it is
an implicit complexity measure (Wegener, 1987). Sensitivity in this sense has
been shown to correlate with generalization in neural networks (Franco, 2001),
and has been extended for use with practical NLP datasets (Anonymous, 2021).
In this section we discuss the intersection of our theory with sensitivity
analysis, highlighting limitations in sensitivity analysis for sampled
datasets that could be fruitfully addressed in future work.

For a boolean vector $x$, let $x^{i}$ be the _Hamming neighbor_ of $x$ at
dimension $i$: i.e., the vector where $x_{i}$ has been flipped and all other
bits remain the same. Consider $f:\\{0,1\\}^{d}\to\\{0,1\\}$. The _sensitivity
set_ $S(f,x)$ is the set of Hamming neighbors of $x$ with different labels:

$S(f,x)=\left\\{i\in[n]\mid f(x)\neq f(x^{i})\right\\}.$ (2)

The _local sensitivity_ $s(f,x)$ is simply the size of this set:
$s(f,x)=\left\lvert S(f,x)\right\rvert$. Finally, the general sensitivity is
the maximum of this quantity over all inputs in the function:

$s(f)=\max_{x}s(f,x).$ (3)

It must be that $0\leq s(f)\leq n$. Functions with $0$ sensitivity must be
constant. An example of a maximum sensitivity function is parity, where for
every pair of Hamming neighbors $x,x^{\prime}$, $f(x)\neq f(x^{\prime})$. A
variety of related measures such as block sensitivity and mean sensitivity
have also been studied. The recently proven Sensitivity Conjecture (Huang,
2019) establishes a polynomial relationship between standard sensitivity and
block sensitivity, which are themselves known to be related to several other
complexity measures, such as degree.

#### Significance of Sensitivity

In our case, the effect of local editing on a dataset can be understood in
terms of sensitivity. Imagine a boolean function
$f:\\{0,1\\}^{d}\to\\{0,1\\}$, from which we draw $n$ samples
$\langle\mathbf{x},y\rangle$. If these samples are drawn _i.i.d._ uniformly
over $\\{0,1\\}^{d}$, then the probability of observing any Hamming neighbors
goes to $0$ rapidly with $d$.101010This is essentially the curse of
dimensionality. Thus, it is possible to pick a low sensitivity function that
can perfectly fit the data. In this sense, the true sensitivity of $f$ is
likely _underspecified_ by the training dataset.

Imagine we give this data to a learner with inductive bias resembling some
variant of Occam’s Razor. If the learner’s notion of complexity is correlated
with sensitivity (which many complexity measures are), then the learner will
favor low sensitivity decision boundaries. Thus, the fact that sensitivity is
underspecified in the training data is a problem if the gold-standard function
has high or even medium sensitivity, as the inductive bias of the learning
algorithm may favor low-sensitivity alternatives.

Contrast this with a dataset where some local neighborhoods in the discrete
input space have been filled in with local edits. Under this setup, the set of
observed neighbors around a point $x$ provide a lower bound on $s(f,x)$. In
turn, $s(f,x)$ provides a lower bound on the global sensitivity $s(f)$. In
this sense, $s(f)$ is no longer underspecified by the dataset.

In this discussion we have used _underspecified_ in an informal way; there is
no precise measure of the sensitivity of a sampled dataset (as opposed to a
fully-specified function), particularly when generalizing from finite boolean
functions to natural language inputs. Attempts to generalize sensitivity to
natural language have done so by leveraging large language models to generate
neighbors from which sensitivity can be estimated (Anonymous, 2021).
Resampling data in this way can give reasonable estimates of the sensitivity
of the underlying task, but it is fundamentally incompatible with measuring
dataset artifacts of the kind we discuss in this paper, as the generative
model can fill in parts of the data distribution that are missing due to
sampling bias, giving a higher estimate of sensitivity than is warranted by
the sampled dataset.

##  6 Other Mitigation Techniques

In this section we briefly discuss the implications of our theoretical
analysis for other artifact mitigation techniques that have been proposed in
the literature. Our analysis in this section is not rigorous and is meant only
to give high-level intuition or potential starting points for future work.

#### More annotators

One suggested mitigation technique for dataset artifacts is to increase the
number of annotators Geva et al. (2019). Especially when people generate the
text that is used in a dataset, there can be substantial person-specific
correlations between features and labels. Having more annotators washes out
those correlations in aggregate, making the data less biased overall.

We briefly analyze this procedure using our rejection sampling framework. For
simplicity, we have so far only considered a single possible rejection
probability, where an instance is rejected with probability $r_{i}$ if
$x_{i}=1$ and $y=0$. If we introduce additional rejection probabilities for
the other three possible combinations of values for $x_{i}$ and $y$, there
will be the possibility that some rejections balance out other rejections. We
can model multiple annotators by splitting a dataset into $k$ different slices
that have their own bias vectors $\mathbf{r}$. If the $\mathbf{r}$ vectors are
uncorrelated, it seems likely that as $k$ increases, the probability that
$\hat{p}(y|x_{i})$ deviates from $p_{u}(y|x_{i})$ tends towards zero. Even in
our simplistic model, if we assume a sparse $\mathbf{r}$, averaging more and
more of them will make the deviation tend toward zero, if the non-zero
dimensions are uncorrelated.

However, if the $\mathbf{r}$ vectors are correlated, increasing the number of
annotators will not produce data reflecting the competency assumption. When
might the $\mathbf{r}$ vectors be correlated? This could happen due to
societal biases, word usage frequencies, or priming effects from data
collection instructions given to all annotators. Surely across any pool of
annotators there will be some dimensions along which $\mathbf{r}$ values are
correlated, and other dimensions along with they are not. Increasing the
number of annotators thus helps mitigate the problem, but does not solve it
completely.

#### Data filtering

A recent trend is to remove data from a training set that is biased in some
way in order to get a model that generalizes better Bras et al. (2020);
Swayamdipta et al. (2020); Oren et al. (2020). While this method can be
effective for very biased datasets, it is somewhat unsatisfying to completely
remove entire instances because there is aggregate dataset bias in a single
feature. In the extreme case where $r_{i}\approx 1$, such as with _“nobody”_
in SNLI (Fig. 1), this process could effectively remove $x_{i}$ from the
observed feature space.

To understand the effect of these automated methods on our view of dataset
artifacts, we repeat the analysis from Section 4.1 on data that was classified
as “ambiguous” according to Dataset Cartography (Swayamdipta et al., 2020).
This data was shown in earlier work to provide better generalization when used
as training data compared to the original training set. The ambiguous
instances did not have a balanced label distribution, so we downsampled the
data to make it balanced, then similarly downsampled the whole training data
to get the same number of instances as the balanced ambiguous set.

The resulting artifact plots are shown in Figure 3. As can be seen, the
“ambiguous” instances have many fewer deviations from the competency
assumption, across the entire range of our hypothesis test. It is not just
high PMI values that are getting corrected by finding ambiguous instances
(which would correspond to a lowering of the top points only); all statistical
deviations are impacted. This effect is striking, and it further corroborates
our arguments about the importance of the competency
assumption.111111Comparing the lower part of Figure 3 to Figure 1 also
corroborates that larger datasets are more likely to have artifacts. With 24%
of the data there are many fewer artifacts.

Figure 3: Statistical artifacts in ambiguous instances (Swayamdipta et al.,
2020) (above) versus a random (same-size) sample from the SNLI training set
(below). The filtering done by ambiguous instance detection targets
statistical artifacts across the whole range of the statistical test, not just
high PMI values.

##  7 Other Related Work

#### Theoretical analysis of bias

Several recent works explore sources and theoretical treatments of bias or
spurious correlations in NLP Shah et al. (2020); Kaushik et al. (2020). Our
work differs in that we introduce a competency assumption and explore its
implications. This puts our work more squarely in the domain of covariate
shift—the rejection sampling procedure we analyze changes the distribution
over inputs, not the labeling function. This change in input distribution
leads to a difference in the observed _marginal_ probability $p(y|x_{i})$, but
not the true $p(y|\mathbf{x})$ itself. The literature on covariate shift is
vast, and discussing it is beyond the scope of this work Quionero-Candela et
al. (2009).

#### Competent models

An interesting question is whether we can introduce a “competency inductive
bias” into models, to discourage leveraging individual features for making
predictions. In linear models, one can simply remove all single features and
only give the model access to complex feature interactions, though even this
could permit the model to leverage correlations between features to
effectively use single features for making predictions. The closest works we
are aware of to making a competency assumption in a modern neural model are
methods that ensemble weak models together with strong models during training,
while using only the strong models for evaluation; presumably the weak models
would pick up on simple feature correlations, and the strong models would be
discouraged from using them (Clark et al., 2020; Dagaev et al., 2021). Other
works use ensembles with models targeted at known sources of data artifacts,
but these are less close to a competency assumption Clark et al. (2019b);
Karimi Mahabadi et al. (2020).

##  8 Conclusion

The more NLP models advance, the better they are at learning the statistical
patterns in NLP datasets. This is problematic for language understanding
research if those statistical patterns allow a model to bypass linguistic
competence. We have formalized this intuition into a class of problems which
we call _competency problems_ , arguing that for any language understanding
task, _all_ correlations between simple features and class labels are
spurious. Collecting data that matches this assumption is challenging, but we
have provided theoretical analysis that can inform future data collection
efforts that target competency problems.

We conclude with some final thoughts on general best practices for data
collection, informed by the analysis in this paper. If annotators are
generating text for some data collection task, find ways to decrease priming
effects. This could involve using images as prompts instead of text Novikova
et al. (2017); Weller et al. (2020), or randomly sampling words that should be
included in the generated text. If already-existing text is being collected
and annotated, make local edits to the text while monitoring the sensitivity
of those edits according to the guidelines in Section 5. But because local
edits have the potential to introduce bias, consider developing two separate
local edit methodologies, or groups of annotators, and use one for training
data and a separate one for test data, to minimize the potential for spurious
correlations to arise between training features and test labels.

## References

  * Anonymous (2021) Anonymous. 2021.  Sensitivity as a complexity measure for sequence classification tasks.  Anonymous preprint under review.
  * Bonferroni (1936) C. E. Bonferroni. 1936.  Teoria statistica delle classi e calcolo delle probabilita.  _Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali di Firenze_ , 8:3–62.
  * Bowman et al. (2015) Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. 2015\.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 632–642, Lisbon, Portugal. Association for Computational Linguistics.
  * Bras et al. (2020) Ronan Le Bras, Swabha Swayamdipta, Chandra Bhagavatula, Rowan Zellers, Matthew E. Peters, Ashish Sabharwal, and Yejin Choi. 2020.  Adversarial filters of dataset biases.  In _ICML_.
  * Buolamwini and Gebru (2018) Joy Buolamwini and Timnit Gebru. 2018.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In _FAT_.
  * Chen et al. (2016) Danqi Chen, Jason Bolton, and Christopher D. Manning. 2016.  A thorough examination of the CNN/Daily Mail reading comprehension task.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2358–2367, Berlin, Germany. Association for Computational Linguistics.
  * Clark et al. (2019a) Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. 2019a.  Boolq: Exploring the surprising difficulty of natural yes/no questions.  In _NAACL_.
  * Clark et al. (2019b) Christopher Clark, Mark Yatskar, and Luke Zettlemoyer. 2019b.  Don’t take the easy way out: Ensemble based methods for avoiding known dataset biases.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4069–4082, Hong Kong, China. Association for Computational Linguistics.
  * Clark et al. (2020) Christopher Clark, Mark Yatskar, and Luke Zettlemoyer. 2020.  Learning to model and ignore dataset bias with mixed capacity ensembles.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3031–3045, Online. Association for Computational Linguistics.
  * Costa-jussà et al. (2019) Marta R. Costa-jussà, Christian Hardmeier, Will Radford, and Kellie Webster, editors. 2019.  _Proceedings of the First Workshop on Gender Bias in Natural Language Processing_. Association for Computational Linguistics, Florence, Italy.
  * Dagaev et al. (2021) Nikolay Dagaev, Brett D. Roads, Xiaoliang Luo, Daniel N. Barry, Kaustubh R. Patil, and Bradley C. Love. 2021.  A too-good-to-be-true prior to reduce shortcut reliance.
  * Dagan et al. (2005) Ido Dagan, Oren Glickman, and B. Magnini. 2005.  The pascal recognising textual entailment challenge.  In _MLCW_.
  * Davidson et al. (2019) Thomas Davidson, Debasmita Bhattacharya, and Ingmar Weber. 2019.  Racial bias in hate speech and abusive language detection datasets.  In _Proceedings of the Third Workshop on Abusive Language Online_ , pages 25–35, Florence, Italy. Association for Computational Linguistics.
  * Dua et al. (2019) Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019.  DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2368–2378, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Franco (2001) Leonardo Franco. 2001.  A measure for the complexity of boolean functions related to their implementation in neural networks.  _arXiv preprint cond-mat/0111169_.
  * Gardner et al. (2020) Matt Gardner, Yoav Artzi, Victoria Basmov, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, Nitish Gupta, Hannaneh Hajishirzi, Gabriel Ilharco, Daniel Khashabi, Kevin Lin, Jiangming Liu, Nelson F. Liu, Phoebe Mulcaire, Qiang Ning, Sameer Singh, Noah A. Smith, Sanjay Subramanian, Reut Tsarfaty, Eric Wallace, Ally Zhang, and Ben Zhou. 2020.  Evaluating models’ local decision boundaries via contrast sets.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1307–1323, Online. Association for Computational Linguistics.
  * Geva et al. (2019) Mor Geva, Yoav Goldberg, and Jonathan Berant. 2019.  Are we modeling the task or the annotator? an investigation of annotator bias in natural language understanding datasets.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1161–1166, Hong Kong, China. Association for Computational Linguistics.
  * Gururangan et al. (2018) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. 2018.  Annotation artifacts in natural language inference data.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 107–112, New Orleans, Louisiana. Association for Computational Linguistics.
  * Huang (2019) Hao Huang. 2019.  Induced subgraphs of hypercubes and a proof of the sensitivity conjecture.
  * Huang et al. (2020) William Huang, Haokun Liu, and Samuel R. Bowman. 2020.  Counterfactually-augmented SNLI training data does not yield better generalization than unaugmented data.  In _Proceedings of the First Workshop on Insights from Negative Results in NLP_ , pages 82–87, Online. Association for Computational Linguistics.
  * Jia and Liang (2017) Robin Jia and Percy Liang. 2017.  Adversarial examples for evaluating reading comprehension systems.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2021–2031, Copenhagen, Denmark. Association for Computational Linguistics.
  * Karimi Mahabadi et al. (2020) Rabeeh Karimi Mahabadi, Yonatan Belinkov, and James Henderson. 2020.  End-to-end bias mitigation by modelling biases in corpora.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8706–8716, Online. Association for Computational Linguistics.
  * Kaushik et al. (2020) Divyansh Kaushik, Amrith Rajagopal Setlur, E. Hovy, and Zachary Chase Lipton. 2020\.  Explaining the efficacy of counterfactually-augmented data.  _ArXiv_ , abs/2010.02114.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.  _ArXiv_ , abs/1909.11942.
  * Lin et al. (2019) Kevin Lin, Oyvind Tafjord, Peter Clark, and Matt Gardner. 2019.  Reasoning over paragraph effects in situations.  In _Proceedings of the 2nd Workshop on Machine Reading for Question Answering_ , pages 58–62, Hong Kong, China. Association for Computational Linguistics.
  * Liu et al. (2019) Y. Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, M. Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Morris et al. (2020) John Morris, Eli Lifland, Jin Yong Yoo, Jake Grigsby, Di Jin, and Yanjun Qi. 2020\.  Textattack: A framework for adversarial attacks, data augmentation, and adversarial training in nlp.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 119–126.
  * Novikova et al. (2017) Jekaterina Novikova, Ondřej Dušek, and Verena Rieser. 2017.  The E2E dataset: New challenges for end-to-end generation.  In _Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 201–206, Saarbrücken, Germany. Association for Computational Linguistics.
  * Oren et al. (2020) Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020\.  Improving compositional generalization in semantic parsing.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2482–2495, Online. Association for Computational Linguistics.
  * Poliak et al. (2018) Adam Poliak, Jason Naradowsky, Aparajita Haldar, Rachel Rudinger, and Benjamin Van Durme. 2018.  Hypothesis only baselines in natural language inference.  In _Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics_ , pages 180–191, New Orleans, Louisiana. Association for Computational Linguistics.
  * Quionero-Candela et al. (2009) Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and N. Lawrence. 2009.  _Dataset Shift in Machine Learning_.  MIT Press.
  * Ribeiro et al. (2018) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018.  Anchors: High-precision model-agnostic explanations.  In _AAAI_.
  * Rudinger et al. (2018) Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme. 2018.  Gender bias in coreference resolution.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 8–14, New Orleans, Louisiana. Association for Computational Linguistics.
  * Sennrich (2017) Rico Sennrich. 2017.  How grammatical is character-level neural machine translation? Assessing MT quality with contrastive translation pairs.
  * Shah et al. (2020) Deven Santosh Shah, H. Andrew Schwartz, and Dirk Hovy. 2020.  Predictive biases in natural language processing models: A conceptual framework and overview.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5248–5264, Online. Association for Computational Linguistics.
  * Shekhar et al. (2017) Ravi Shekhar, Sandro Pezzelle, Yauhen Klimovich, Aurélie Herbelot, Moin Nabi, Enver Sangineto, and Raffaella Bernardi. 2017.  Foil it! Find One mismatch between image and language caption.
  * Sugawara et al. (2018) Saku Sugawara, Kentaro Inui, Satoshi Sekine, and Akiko Aizawa. 2018.  What makes reading comprehension questions easier? In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4208–4219, Brussels, Belgium. Association for Computational Linguistics.
  * Swayamdipta et al. (2020) Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang, Hannaneh Hajishirzi, Noah A. Smith, and Yejin Choi. 2020.  Dataset cartography: Mapping and diagnosing datasets with training dynamics.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9275–9293, Online. Association for Computational Linguistics.
  * Tafjord et al. (2019) Oyvind Tafjord, Matt Gardner, Kevin Lin, and Peter Clark. 2019.  QuaRTz: An open-domain dataset of qualitative relationship questions.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5941–5946, Hong Kong, China. Association for Computational Linguistics.
  * Wallace et al. (2019) Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. 2019.  Universal adversarial triggers for attacking and analyzing NLP.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2153–2162, Hong Kong, China. Association for Computational Linguistics.
  * Wang et al. (2019) Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019.  Superglue: A stickier benchmark for general-purpose language understanding systems.  In _NeurIPS_.
  * Wegener (1987) Ingo Wegener. 1987.  _The complexity of Boolean functions_.  Wiley.
  * Weller et al. (2020) Orion Weller, Nicholas Lourie, Matt Gardner, and Matthew Peters. 2020.  Learning from task descriptions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1361–1375, Online. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender bias in coreference resolution: Evaluation and debiasing methods.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 15–20, New Orleans, Louisiana. Association for Computational Linguistics.