# Separating the Wheat from the Chaff with Bread:
An open-source benchmark and metrics to detect redundancy in text

Isaac Caswell
Google Research
<EMAIL_ADDRESS>
&Lisa Wang
Google DeepMind
<EMAIL_ADDRESS>
&Isabel Papadimitriou
Computer Science Department
Stanford University
<EMAIL_ADDRESS>
###### Abstract

Data quality is a problem that perpetually resurfaces throughout the field of
NLP, regardless of task, domain, or architecture, and remains especially
severe for lower-resource languages. A typical and insidious issue, affecting
both training data and model output, is data that is repetitive and dominated
by linguistically uninteresting boilerplate, such as price catalogs or
computer-generated log files. Though this problem permeates many web-scraped
corpora, there has yet to be a benchmark to test against, or a systematic
study to find simple metrics that generalize across languages and agree with
human judgements of data quality. In the present work, we create and release
Bread, a human-labeled benchmark on repetitive boilerplate vs. plausible
linguistic content, spanning 360 languages. We release several baseline Cred
(Character REDundancy) scores along with it, and evaluate their effectiveness
on Bread. We hope that the community will use this resource to develop better
filtering methods, and that our reference implementations of Cred scores can
become standard corpus evaluation tools, driving the development of cleaner
language modeling corpora, especially in low-resource languages. 111Our data
for the BREAD benchmark and code for the CRED scores suite is at
https://github.com/toizzy/bread

##  1 Introduction

In this paper, we introduce a benchmark and propose a suite of metrics to help
identify a common facet of low-quality data: repetitive boilerplate that is
not reflective of natural linguistic content. Large language corpora scraped
from the internet are becoming invaluable tools as self-supervised language
modeling has gained prominence as a driving force of advancements in NLP
(Devlin et al., 2018; Chowdhery et al., 2022; Brown et al., 2020, inter alia).
In the case of many low-resource languages, noisy in-language data often makes
up a significant proportion of any scraped corpus (Kreutzer et al., 2022).
Very often, this noise is in the form of repetitive boilerplate: uninteresting
data without linguistic diversity, such as a long list of similar products
from an e-commerce website. Automatically reducing repetitive boilerplate in
low-resource language corpora remains an important problem to extend NLP to
the thousands of languages currently underserved by language technology.

Figure 1: Character ngram based metrics compare the ngram frequency histogram
between natural text and repetitive text, and assign a score of how repetitive
it is. In this toy example, the character 6-gram histogram on the left is
clearly distinguishable from the more natural distribution on the right. The
Cred metrics rely on this intuition, applying simple metrics based on ngram
frequency in order to detect repetitive boilerplate data in a language-
agnostic manner.

To address the problem of redundant boilerplate, our contributions in the
current work are two-fold:

  1. 1.

We release Bread (Boilerplate and Redundancy Evaluation on Assorted
Documents), the first benchmark to measure redundancy and boilerplate in text;

  2. 2.

We test and open-source Cred (Character REDundancy) scores, a suite of
interpretable, fast, language-agnostic metrics for detecting repetition in
documents.

Since data noise disproportionately affects low-resource languages, we only
consider metrics that are language-agnostic (meaning their performance doesn’t
depend on any particular language). As such, we do not consider neural methods
for the baselines released with Bread: though they are more expressive than
surface-level metrics, they rely on high-quality training data, and are
therefore less reliable for low-resource languages where the training data is
scarce, noisy, or highly overlapping with eval or model-training data.
Similarly, neural metrics struggle with interpretability and reproducibility.

The difference between a paragraph of natural text and a long, repetitive list
does not depend on the source language or the particular thing that is
repeating. Therefore, it is possible to build language-agnostic metrics that
ignore textual features entirely, and operate purely on the token-frequency
distribution. Using this intuition, we explore three ngram-based metrics:
type-token ratio (TTR), measuring the percentage of unique ngrams; ngram-
moment, measuring the peakiness of the frequency distribution; and ngram-
Zipfianness, measuring the distance from the expected frequency distribution
of natural language.

Our objective is to detect redundant language within one document. This is
different from a commonly studied problem in data quality management, where
redundancy refers to a dataset containing many redundant copies of similar
natural documents. We open-source the Bread benchmark and the Cred metrics,
making it a replicable resource for the community.

##  2 Related Work

In the field of Data-Quality management, quality scores are used for
measurement and improvement, and often incorporated into an iterative process
(Wang, 1998). For NLP, there are many existing works highlighting the
importance of cleaning data for training neural models (Khayrallah and Koehn,
2018; Junczys-Dowmunt, 2018a; Wang et al., 2018b). Many denoising approaches
rely on classifiers (Chen and Huang, 2016; Chen et al., 2016; Wang et al.,
2017) or cross-entropy distance between models (Moore and Lewis, 2010; Axelrod
et al., 2011; van der Wees et al., 2017; Axelrod, 2017), an approach often
applied to data weighting and curriculum training (Zhang et al., 2017; Wang et
al., 2018a, 2019). There are neural diversity metrics, like Miranda et al.
(2022), which uses the cosine distance between Task2Vec embeddings (Achille et
al., 2019), and has been applied to measure LLM output diversity (Lee et al.,
2023).

Although data noise has always been a recognized problem, it has become a more
pressing issue in recent years, as models have become more and more
expressive, therefore also more capable of memorizing noise. Statistical
machine translation models were more robust to data noise and tended only to
benefit from bigger data (Goutte et al., 2012) (with a few exceptions, like
Taghipour et al. (2011)), and works on data filtering were usually focused on
improving training efficiency (for instance, Johnson et al. (2007)). Despite
their generally higher performance, neural models tended to be much more
sensitive to data noise (Khayrallah and Koehn, 2018), possibly as a result of
being able to memorize statistical outliers (Arpit et al., 2017; Feldman and
Zhang, 2020). Even early versions of Paracrawl damaged MT performance Junczys-
Dowmunt (2018b); Schamper et al. (2018), and the winners of the yearly WMT
campaign tend to rely heavily on data filtering (Junczys-Dowmunt, 2018a;
Chaudhary et al., 2019; Lu et al., 2020; Lo and Joanis, 2020). As a result,
there have been several data filtering shared tasks in WMT (Koehn et al.,
2018, 2019, 2020), and open-sourcing of various iterations of data cleaner
Bicleaner (Esplà-Gomis et al., 2020; Ramírez-Sánchez et al., 2020; Zaragoza-
Bernabeu et al., 2022), which use a variety of approaches, including bilingual
dictionaries, random forests, and neural models.

While neural metrics or complex ensembles like Bicleaner are often effective,
they 1) are harder to interpret; 2) may filter on artifacts like domain,
rather than quality; 3) will tend only to work for languages they have
explicitly been trained on; and 4) cannot be replicated between works unless a
public implementation is released. For this reason, the baseline metrics
released with Bread are simple, interpretable, surface-level metrics, that
work independent of language and domain.

A token-based metric to measure the diversity and redundancy of token ngrams
between documents in a corpus (rather than within segments of one document) is
self-Bleu (Zhu et al., 2018), which is based on the widely used Bleu score
Papineni et al. (2002). On a more granular level of character ngrams, the ChrF
(Popović, 2015) and ChrF++ (Popović, 2017) metrics measure similarity between
documents, correlating better with human judgement than token-level metrics
like Bleu, especially for low-resource and highly-inflecting languages (Kocmi
et al., 2021; Freitag et al., 2022; Bapna et al., 2022; Caswell et al., 2020).
We follow this intuition and use character-ngram metrics. The frequency moment
score defined in the present work is similar to segment-level ChrF applied
with itself as its own reference.

Perhaps the most similar approaches to those in the present work come from a
separate field, namely detecting redundancy and diversity in relational or
tabular data (Ehrlinger and Wöß, 2022). Batista and Salgado (2007) and
Ehrlinger and Wöß (2019) define interpretable minimality scores to measure
redundancy at a schema-level for tabular data, based on cluster density, which
is equivalent to the TTR in the present work.

##  3 Bread: Dataset and Annotation

We release Bread (Boilerplate and Redundancy Evaluation on Assorted
Documents), an expert-annotated dataset spanning 360 languages, to tune and
benchmark methods for filtering repetitive boilerplate. Bread consists of
randomly-chosen documents from the multilingual, common-crawl-based MadLad-400
dataset (Kudugunta et al., 2023), which are then annotated by expert NLP-
practitioner annotators.

Our annotation schema consists of two high-confidence classes and two low-
confidence classes. The high-confidence classes are 1) Rep, repetitive
boilerplate (N=449), and 2) OK, natural text (N=863). To keep the examples in
Rep and OK high-confidence, we also use two low-confidence codes: Boil, for
documents that are clearly non-linguistic boilerplate or noise, but are not
necessarily repeating (N=499); and unk for where the annotator was not sure
(N=3339). Documents labeled as unk were discarded. See Appendix Table 2 for
examples of each class. The examples labeled OK cover 360 languages, with no
individual language having more than 6 samples; the language distribution of
the other three codes are harder to measure, since they are often
nonlinguistic content or noisy ambiguous text. Examples are capped at 5000
character for ease of processing.

Bread is split into a tune and a test set, each with 1000 documents. We
propose two benchmarks, scored with F1 on the following binary prediction
problems:

  1. 1.

Bread-Repeat: positive class is OK; negative is Rep.

  2. 2.

Bread-Noisy: positive class is OK; negative is union of Rep and Boil.

##  4 Methods

Figure 2: F1 scores for the three metrics proposed in this work, for all four
combinations of tuning and testing on Bread-Repeat and Bread-Noisy. The
reported values are the average of the top ten parameter settings on the
tuning set. Error bars represent 95% confidence intervals.

We explore three well-studied, straightforward metrics based on ngram
frequency distributions and evaluate their effectiveness in the domain of
measuring repetitive boilerplate. We explore both character ngrams and token
ngrams, as well as combinations of the two. As with Bleu (Papineni et al.,
2002), we consider using multiple $n$-gram lengths at once, and combining
these scores by averaging them. By construction, all metrics assign a higher
score to noisier text.

The input to all our metrics is the smoothed frequency distribution of ngrams
within a document. Distributions of ngrams tend to be noisier for shorter
texts, so we apply Laplace smoothing with parameter $\lambda$, and clip the
distribution with $\epsilon$-thresholding (keeping only ngrams with
probability over some $\epsilon$ (Freitag et al., 2023)). Let $f_{n}^{(i)}$ be
the raw frequency of the $i$th most common $n$-gram. We define our smoothed
frequency distribution as:

$\displaystyle\tilde{f}_{n}^{(i)}\propto\left(f_{n}^{(i)}+\lambda\right)\mathbbm{1}\\{f_{n}^{(i)}>\epsilon\\}$
(1)

This said, the authors would like to foreshadow that this distribution
clipping and smoothing end up not being very important parameters for well-
performing metrics, so the reader may safely ignore this and imagine that the
metrics are a function of raw frequency.

The metrics we explored are as follows:

#### TTR:

As an intuitive and well-known baseline metric, we use the Token-Type Ratio
(TTR) (Templin, 1957), which is the fraction of unique tokens in a document
(types) over the total number of tokens. We use n-grams as tokens.

#### Frequency Moment score:

The second score we consider is the generalized moment of the frequency
probability distribution, the sum of all frequencies when applying a with a
nonlinearity $g(x)$. For a character n-gram with length $n$, the momet score
is defined as:

$\displaystyle m_{n}=\sum_{i}g\left(\tilde{f}_{n}^{(i)}\right)$ (2)

The nonlinearity $g(x)$ is a parameter we can vary to best fit out benchmark.
Intuitively, setting any superlinear $g(x)$, this metric measures redundancy,
or peakiness, of the ngram counts, as the score is larger when there is more
weight in the head of the distribution. When $g(x)=x^{k}$, the score
corresponds to the $k$th moment of the distribution; when $g(x)=-x\log(x)$, it
corresponds to the entropy.

#### Zipfianness:

Human languages have a largely consistent word distribution: across languages,
the empirical frequency of how often different words appear follows a Zipfian,
or power-law distribution, where the word in frequency rank $r$ has frequency
roughly proportional to $\frac{1}{r}$ (Zipf, 1936; Piantadosi, 2014). For
example, in English the most common word “the” occurs around double the rate
of the second most common word “of”. To test whether a document is distributed
like natural text, we can check whether its ngram distribution matches the
empirical ngram distribution of a human language, which we estimate as a
function of the n-gram length with a slight modification of the classic
$\frac{1}{r}$ value (details in Appendix D). 222We also experiment with the
empirical token distribution from a random sample of 10,000 English documents
from MadLad-400-clean, and find the results to be the same (but much more
painful to calculate), so for simplicity we focus only on the analytic
approximation in this paper. Therefore, we define the Zipfianness score as
follows:

$\displaystyle
z_{n}=\sum_{i}d\left(\hat{f}_{n}^{(i)},\tilde{f}_{n}^{(i)}\right)$ (3)

Where $\hat{f}_{i}$ is the estimated frequency of the $i$th most common token,
and $d(x,y)$ is a distance metric. For $d(x,y)$, we consider
$|x-y|^{2},\log(|x-y|),\log^{2}(|x-y|)$ and $\textrm{JSD}(x,y)$. We initially
also considered KL divergence (in both directions) and absolute distance, but
they proved less effective.

###  4.1 Compensating for Length Dependency

All three of these scores are dependent on the length of the document and are
all minimized when the document consists only of unique n-grams (i.e. input
distribution is uniform). Therefore, we normalize the score on a candidate
document by what the score would be for a document of the same length with
only unique n-grams. This leads to the interpretation of something like “How
much more redundant is this document than a natural document of the same
length?". However, since natural languages are drawn from a finite and non-
uniform set of symbols, the uniform distribution becomes an increasingly bad
approximation of a “natural" document as the document length increases, and
leads to the reverse skew of what the length normalization was originally
trying to address. To compensate for this, we introduce a simple asymptote for
the number of tokens in a document, and normalize by the uniform distribution
for a document with that length. This approach is chosen over the more typical
approach of a fixed-width sliding window over characters, as is often done
with TTR (Kettunen, 2014), because Bread has a significant range in document
lengths, so we expect this approach to capture the variation in scores more
cleanly. Details are in Appendix Section A.

###  4.2 Grid Search

Each metric is dependent on the parameters used to smooth and nonlinearize the
frequency distribution, the length normalization asymptote, and the
appropriate threshold when used as a classifier. Therefore, we split the
dataset into a 50/50 validation/test split, and perform a grid search on the
validation split, optimizing for F1 score. Variants of the scores optimized
for different metrics are also open-sourced (§6); details in Appendix B.

##  5 Baseline Metric Results on Bread

As shown in Fig. 2, all metrics have fairly good correlation with human
judgement, even when they are trained on the out-of-domain split of Bread (the
off-diagonal entries). For detecting repetition alone (Bread-Repeat; top row),
both the moment score and the Zipfianness score performed about 5% better on
both tuning and test sets than TTR. When detecting both noise and boilerplate
(Bread-Noisy), the difference in scores is more pronounced, with Zipfianness
outperforming TTR by 9% on the test split. The moment score, which like TTR is
only able to detect redundancy but not other types of noise, barely
outperforms TTR.

It is worth noting that for questions of data noise, there is a large
difference between apparently close scores, if they are both close to 100.
Caswell et al. (2020) note (§Massive Class Imbalances: 99% Accuracy Is Not
Enough) that if a Language Identification model has a precision of 99.0, using
it to generate a dataset for a typical low-resource language will yeild a
dataset with just under a tenth of a percent of sentences in the target
language. Increasing this precision to 99.9%, though under 1% better in
additive terms, is a 10x improvement in dataset precision. Keeping this in
mind, we see that although we have a ways to go with better data quality
scores, the improvement in noise detection from 78 F1 to 85 F1 is quite
substantial!

For a qualitative understanding of what scores on Bread look like, one can
refer to Figure 3, which shows the moment score as a function of length, along
with the decision boundary. Details of the best hyperparameters per ngram
length are given in Appendix Table 5.

###  5.1 Which Parameters Worked the Best?

Unsurprisingly, the most important parameter was the choice of n-gram
length(s). Our initial grid search went over a deep grid of different values.
However, since many of these factors ended up not being very important, they
led to overfitting and poor test scores. Therefore, for the final values, we
re-ran the grid search with a very limited set of parameters (§B). Findings
from both rounds are summarized here:

  * •

n-grams: For the purely repetition-based metrics (TTR, Moment), the most
effective n-gram length seemed to be anything of length 6-grams and up. For
Zipfianness, the peak was considerably earlier, at 4-grams and 5-grams. The
best single n-gram value for across all approaches would therefore be a 5-gram
or 6-gram, similar to the finding by Popović (2015) that 6-grams corresponded
the best with human-judged quality for ChrF. Ensembles of different types of
n-grams usually achieved slightly higher quality, but the improvements were
minor.

  * •

Smoothing: There was no obvious pattern to the best smoothing value $\lambda$.

  * •

Distribution truncation: The optimal $\epsilon$ value for $\epsilon$-clipping
was almost always 0, and the optimal $k$ for top-k clipping was almost always
$\infty$. We conclude that using the full distribution is generally optimal,
and omitted distribution truncation in the final grid search.

  * •

Nonlinearity: The best nonlinearity for the moment score tended to be $x^{2}$,
corresponding nicely with the variance, though the squared entropy
$(x\log(x))^{2}$, $x^{1.5}$, and $x^{3}$ also frequently came out on top for
different settings of the other parameters. The best distance function for
Zipfianness was generally the squared distance, though $\log(|x-y|)$ also
performed well.

  * •

lengthnorm asymptote: The best asymptote for the document length (used when
normalizing by length; §4.1) was usually 2000.

Figure 3: Moment scores on Bread as a function of document length, with the
learned decision boundary in green, demonstrating how moment scores
effectively separate noisy data from clean data along the y-axis. Each point
represents a document in Bread, with the OK labels in blue, Rep labels in red,
and Boil labels in orange. The cluster at the right reflects the truncation of
Bread documents at 5000 characters.

###  5.2 CRED as a Metric for Data Quality

To validate these metrics on existing datasets and to demonstrate how they can
be used to assess data quality, we report their average scores on the
MadLad-400 dataset. This resource is an excellent testing ground because it
has both clean and noisy splits, and furthermore covers many very low-resource
languages, where we expect more noise in the data. Results are reported in
Table 1. We make the following observations:

  1. 1.

All three metrics agree that the noisy split indeed has more repetitive
content. This offers more evidence that our metrics are effective at detecting
noise and assessing data quality.

  2. 2.

For low-resource languages (LRL), all metrics indicate that both clean and
noisy splits are noisier compared to the respective splits in high-resource
languages (HRL), which would align with intuition.

  3. 3.

The relative scores also allow us to make the interesting inference that the
clean split of the low-resource languages has a similar noisiness level to the
noisy split of the high-resource languages.

| TTR | moment | zipf.
---|---|---|---
Mad. clean HRL | 0.116 | 0.677 | 0.679
Mad. clean LRL | 0.175 | 0.972 | 0.688
Mad. noisy HRL | 0.136 | 0.802 | 1.064
Mad. noisy LRL | 0.189 | 1.473 | 2.063
Table 1: Scores on the noisy and clean splits of MadLad-400, for 45 high-
resource languages (HRL, >1M documents in the clean split) and 368 low-
resource languages (LRL). All scores show more severe noise for low-resource
languages, and for the noisy split.

##  6 Open-Sourcing

We open-source reference implementations of these metrics. Following the
example of SacreBleu (Post, 2018), each score has a unique signature reporting
all relevant hyperparameters, so it is fully reproducible. In order to suit
different levels of noise and different preferences of precision versus
recall, we release versions of each classifier that have been tuned for F1 on
a balanced version of Bread, as well as a version that has been tuned on the
P4 score (Sitarz, 2022) with Bread upweighted so it is 75% clean data.

##  7 Conclusion

Data quality is an evergreen problem, and as NLP is widening to a growing set
of low-resource languages, where noise is a more severe problem, the need for
more interpretable metrics to asses noise becomes especially prominent. Recent
approaches to highly multilingual technologies like NMT and LangID have
reported severe noise issues for low-resource languages (Caswell et al., 2020;
Bapna et al., 2022), and many publicly available datasets with low-resource
languages in fact contain no in-language content (Kreutzer et al., 2022).
Nonetheless, there was heretofore no public benchmark for boilerplate and
noise detection.The present work introduces Bread, a multilingual, expert-
annotated benchmark for detecting noise. It also investigates several
interpretable, language-agnostic baseline metrics based on character ngram
frequency distributions, as well as their scores on the public dataset
MadLad-400. Finally, it open-sources reference implementations of several
language-agnostic metrics for scoring and classifying data.

## Limitations

While the Bread and the metrics introduced in this paper are useful
approximations, there are many forms of noise they can’t detect. They can’t
detect poor grammar, scrambled text, translationese, toxicity, or other noise
that follows a Zipfian-distribution. Furthermore they can’t detect inter-
example redundancy, for which a better-suited metric would be something like
self-Bleu.

Furthermore, such a metric may not generalize well to all languages. Although
the language-agnostic approach to the creation of the Bread eval set is
constructed to work for all languages, many languages, especially those with
more distinct character sets like Chinese and Japanese, may exhibit unique
forms of noise or token distributions.

Finally, these metrics will tend to be less useful for shorter texts, and
practitioners are cautioned against using them on sentence-level data.

## Ethics Statement

We introduce a benchmark dataset and scoring mechanisms for improving the
quality of low-resource language corpora. Like any metrics based on surface-
level features, our metrics are coarse and do not reflect the subtleties of
different languages. We propose for our CRED scores to be used in a battery of
data quality evaluation methods.

## Acknowledgements

The authors would like to thank the wonderful Ithaka Co-Operative House, which
enabled this collaboration. This research was funded in part by NSF award
number IIS-2128145.

## References

  * Achille et al. (2019) Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Charless C. Fowlkes, Stefano Soatto, and Pietro Perona. 2019.  Task2vec: Task embedding for meta-learning.  _CoRR_ , abs/1902.03545.
  * Arpit et al. (2017) Devansh Arpit, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. 2017.  A closer look at memorization in deep networks.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 233–242. PMLR.
  * Axelrod (2017) Amittai Axelrod. 2017.  Cynical selection of language model training data.  _CoRR_ , abs/1709.02279.
  * Axelrod et al. (2011) Amittai Axelrod, Xiaodong He, and Jianfeng Gao. 2011.  Domain adaptation via pseudo in-domain data selection.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 355–362.
  * Bapna et al. (2022) Ankur Bapna, Isaac Caswell, Julia Kreutzer, Orhan Firat, Daan van Esch, Aditya Siddhant, Mengmeng Niu, Pallavi Baljekar, Xavier Garcia, Wolfgang Macherey, Theresa Breiner, Vera Axelrod, Jason Riesa, Yuan Cao, Mia Xu Chen, Klaus Macherey, Maxim Krikun, Pidong Wang, Alexander Gutkin, Apurva Shah, Yanping Huang, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. 2022.  Building Machine Translation Systems for the Next Thousand Languages.  _arXiv e-prints_ , page arXiv:2205.03983.
  * Batista and Salgado (2007) Maria da Conceição Moraes Batista and Ana Carolina Salgado. 2007.  Information quality measurement in data integration schemas.  In _QDB_ , pages 61–72.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Caswell et al. (2020) Isaac Caswell, Theresa Breiner, Daan van Esch, and Ankur Bapna. 2020.  Language id in the wild: Unexpected challenges on the path to a thousand-language web text corpus.
  * Chaudhary et al. (2019) Vishrav Chaudhary, Yuqing Tang, Francisco Guzmán, Holger Schwenk, and Philipp Koehn. 2019.  Low-resource corpus filtering using multilingual sentence embeddings.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2)_ , pages 261–266, Florence, Italy. Association for Computational Linguistics.
  * Chen and Huang (2016) Boxing Chen and Fei Huang. 2016.  Semi-supervised convolutional networks for translation adaptation with tiny amount of in-domain data.  In _Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning (CoNLL)_ , pages 314–323.
  * Chen et al. (2016) Boxing Chen, Roland Kuhn, George Foster, Colin Cherry, and Fei Huang. 2016.  Bilingual methods for adaptive training data selection for machine translation.  In _AMTA_.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Ehrlinger and Wöß (2019) Lisa Ehrlinger and Wolfram Wöß. 2019.  A novel data quality metric for minimality.  In _Data Quality and Trust in Big Data: 5th International Workshop, QUAT 2018, Held in Conjunction with WISE 2018, Dubai, UAE, November 12–15, 2018, Revised Selected Papers 5_ , pages 1–15. Springer.
  * Ehrlinger and Wöß (2022) Lisa Ehrlinger and Wolfram Wöß. 2022.  A survey of data quality measurement and monitoring tools.  _Frontiers in big data_ , page 28.
  * Esplà-Gomis et al. (2020) Miquel Esplà-Gomis, Víctor M. Sánchez-Cartagena, Jaume Zaragoza-Bernabeu, and Felipe Sánchez-Martínez. 2020.  Bicleaner at WMT 2020: Universitat d’alacant-prompsit’s submission to the parallel corpus filtering shared task.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 952–958, Online. Association for Computational Linguistics.
  * Feldman and Zhang (2020) Vitaly Feldman and Chiyuan Zhang. 2020.  What neural networks memorize and why: Discovering the long tail via influence estimation.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 2881–2891. Curran Associates, Inc.
  * Freitag et al. (2023) Markus Freitag, Behrooz Ghorbani, and Patrick Fernandes. 2023.  Epsilon sampling rocks: Investigating sampling strategies for minimum bayes risk decoding for machine translation.
  * Freitag et al. (2022) Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, Eleftherios Avramidis, Tom Kocmi, George Foster, Alon Lavie, and André FT Martins. 2022.  Results of wmt22 metrics shared task: Stop using bleu–neural metrics are better and more robust.  In _Proceedings of the Seventh Conference on Machine Translation (WMT)_ , pages 46–68.
  * Goutte et al. (2012) Cyril Goutte, Marine Carpuat, and George Foster. 2012.  The impact of sentence alignment errors on phrase-based machine translation performance.  In _Proceedings of the 10th Conference of the Association for Machine Translation in the Americas: Research Papers_ , San Diego, California, USA. Association for Machine Translation in the Americas.
  * Johnson et al. (2007) Howard Johnson, Joel Martin, George Foster, and Roland Kuhn. 2007.  Improving translation quality by discarding most of the phrasetable.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 967–975, Prague, Czech Republic. Association for Computational Linguistics.
  * Junczys-Dowmunt (2018a) Marcin Junczys-Dowmunt. 2018a.  Dual conditional cross-entropy filtering of noisy parallel corpora.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 888–895, Belgium, Brussels. Association for Computational Linguistics.
  * Junczys-Dowmunt (2018b) Marcin Junczys-Dowmunt. 2018b.  Microsoft’s submission to the WMT2018 news translation task: How I learned to stop worrying and love the data.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 425–430, Belgium, Brussels. Association for Computational Linguistics.
  * Kettunen (2014) Kimmo Kettunen. 2014.  Can type-token ratio be used to show morphological complexity of languages?  _Journal of Quantitative Linguistics_ , 21(3):223–245.
  * Khayrallah and Koehn (2018) Huda Khayrallah and Philipp Koehn. 2018.  On the impact of various types of noise on neural machine translation.  In _Proceedings of the 2nd Workshop on Neural Machine Translation and Generation_ , pages 74–83, Melbourne, Australia. Association for Computational Linguistics.
  * Kocmi et al. (2021) Tom Kocmi, Christian Federmann, Roman Grundkiewicz, Marcin Junczys-Dowmunt, Hitokazu Matsushita, and Arul Menezes. 2021.  To ship or not to ship: An extensive evaluation of automatic metrics for machine translation.  In _Proceedings of the Sixth Conference on Machine Translation_ , pages 478–494.
  * Koehn et al. (2020) Philipp Koehn, Vishrav Chaudhary, Ahmed El-Kishky, Naman Goyal, Peng-Jen Chen, and Francisco Guzmán. 2020.  Findings of the WMT 2020 shared task on parallel corpus filtering and alignment.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 726–742, Online. Association for Computational Linguistics.
  * Koehn et al. (2019) Philipp Koehn, Francisco Guzmán, Vishrav Chaudhary, and Juan Pino. 2019.  Findings of the WMT 2019 shared task on parallel corpus filtering for low-resource conditions.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2)_ , pages 54–72, Florence, Italy. Association for Computational Linguistics.
  * Koehn et al. (2018) Philipp Koehn, Huda Khayrallah, Kenneth Heafield, and Mikel L. Forcada. 2018.  Findings of the WMT 2018 shared task on parallel corpus filtering.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 726–739, Belgium, Brussels. Association for Computational Linguistics.
  * Kreutzer et al. (2022) Julia Kreutzer, Isaac Caswell, Lisa Wang, Ahsan Wahab, Daan van Esch, Nasanbayar Ulzii-Orshikh, Allahsera Tapo, Nishant Subramani, Artem Sokolov, Claytone Sikasote, Monang Setyawan, Supheakmungkol Sarin, Sokhar Samb, Benoît Sagot, Clara Rivera, Annette Rios, Isabel Papadimitriou, Salomey Osei, Pedro Ortiz Suarez, Iroro Orife, Kelechi Ogueji, Andre Niyongabo Rubungo, Toan Q. Nguyen, Mathias Müller, André Müller, Shamsuddeen Hassan Muhammad, Nanda Muhammad, Ayanda Mnyakeni, Jamshidbek Mirzakhalov, Tapiwanashe Matangira, Colin Leong, Nze Lawson, Sneha Kudugunta, Yacine Jernite, Mathias Jenny, Orhan Firat, Bonaventure F. P. Dossou, Sakhile Dlamini, Nisansa de Silva, Sakine Çabuk Ballı, Stella Biderman, Alessia Battisti, Ahmed Baruwa, Ankur Bapna, Pallavi Baljekar, Israel Abebe Azime, Ayodele Awokoya, Duygu Ataman, Orevaoghene Ahia, Oghenefego Ahia, Sweta Agrawal, and Mofetoluwa Adeyemi. 2022.  Quality at a glance: An audit of web-crawled multilingual datasets.  _Transactions of the Association for Computational Linguistics_ , 10:50–72.
  * Kudugunta et al. (2023) Sneha Kudugunta, Isaac Caswell, Biao Zhang, Xavier Garcia, Christopher A Choquette-Choo, Katherine Lee, Derrick Xin, Aditya Kusupati, Romi Stella, Ankur Bapna, et al. 2023.  MADLAD-400: A multilingual and document-level large audited dataset.  _Advances in Neural Information Processing Systems_.
  * Lee et al. (2023) Alycia Lee, Brando Miranda, and Sanmi Koyejo. 2023.  Beyond scale: the diversity coefficient as a data quality metric demonstrates llms are pre-trained on formally diverse data.
  * Lo and Joanis (2020) Chi-kiu Lo and Eric Joanis. 2020.  Improving parallel data identification using iteratively refined sentence alignments and bilingual mappings of pre-trained language models.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 972–978, Online. Association for Computational Linguistics.
  * Lu et al. (2020) Jun Lu, Xin Ge, Yangbin Shi, and Yuqi Zhang. 2020.  Alibaba submission to the WMT20 parallel corpus filtering task.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 979–984, Online. Association for Computational Linguistics.
  * Miranda et al. (2022) Brando Miranda, Patrick Yu, Yu-Xiong Wang, and Sanmi Koyejo. 2022.  The curse of low task diversity: On the failure of transfer learning to outperform maml and their empirical equivalence.
  * Moore and Lewis (2010) Robert C. Moore and William Lewis. 2010.  Intelligent selection of language model training data.  In _Proceedings of the ACL 2010 Conference_ , pages 220–224.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Piantadosi (2014) Steven T Piantadosi. 2014.  Zipf’s word frequency law in natural language: A critical review and future directions.  _Psychonomic bulletin & review_, 21:1112–1130.
  * Popović (2015) Maja Popović. 2015.  chrf: character n-gram f-score for automatic mt evaluation.  In _Proceedings of the tenth workshop on statistical machine translation_ , pages 392–395.
  * Popović (2017) Maja Popović. 2017.  chrF++: words helping character n-grams.  In _Proceedings of the Second Conference on Machine Translation_ , pages 612–618, Copenhagen, Denmark. Association for Computational Linguistics.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Ramírez-Sánchez et al. (2020) Gema Ramírez-Sánchez, Jaume Zaragoza-Bernabeu, Marta Bañón, and Sergio Ortiz Rojas. 2020.  Bifixer and bicleaner: two open-source tools to clean your parallel data.  In _Proceedings of the 22nd Annual Conference of the European Association for Machine Translation_ , pages 291–298, Lisboa, Portugal. European Association for Machine Translation.
  * Schamper et al. (2018) Julian Schamper, Jan Rosendahl, Parnia Bahar, Yunsu Kim, Arne Nix, and Hermann Ney. 2018.  The RWTH Aachen University supervised machine translation systems for WMT 2018.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 496–503, Belgium, Brussels. Association for Computational Linguistics.
  * Sitarz (2022) Mikolaj Sitarz. 2022.  Extending f1 metric, probabilistic approach.
  * Taghipour et al. (2011) Kaveh Taghipour, Shahram Khadivi, and Jia Xu. 2011.  Parallel corpus refinement as an outlier detection algorithm.  In _Proceedings of Machine Translation Summit XIII: Papers_ , Xiamen, China.
  * Templin (1957) Mildred C Templin. 1957.  Certain language skills in children; their development and interrelationships.
  * van der Wees et al. (2017) Marlies van der Wees, Arianna Bisazza, and Christof Monz. 2017.  Dynamic data selection for neural machine transaltion.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1400–1410.
  * Wang (1998) Richard Y Wang. 1998.  A product perspective on total data quality management.  _Communications of the ACM_ , 41(2):58–65.
  * Wang et al. (2017) Rui Wang, Masao Utiyama, Lemao Liu, Kehai Chen, and Eiichiro Sumita. 2017.  Instance weighting for neural machine translation domain adaptation.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1482–1488. Association for Computational Linguistics.
  * Wang et al. (2018a) Rui Wang, Masao Utiyama, and Eiichiro Sumita. 2018a.  Dynamic sentence sampling for efficient training of neural machine translation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 298–304, Melbourne, Australia. Association for Computational Linguistics.
  * Wang et al. (2019) Wei Wang, Isaac Caswell, and Ciprian Chelba. 2019.  Dynamically composing domain-data selection with clean-data selection by “co-curricular learning” for neural machine translation.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics_ , pages 1282–1292, Florence, Italy. Association for Computational Linguistics.
  * Wang et al. (2018b) Wei Wang, Taro Watanabe, Macduff Hughes, Tetsuji Nakagawa, and Ciprian Chelba. 2018b.  Denoising neural machine translation training with trusted data and online data selection.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 133–143. Association for Computational Linguistics.
  * Zaragoza-Bernabeu et al. (2022) Jaume Zaragoza-Bernabeu, Gema Ramírez-Sánchez, Marta Bañón, and Sergio Ortiz Rojas. 2022.  Bicleaner AI: Bicleaner goes neural.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 824–831, Marseille, France. European Language Resources Association.
  * Zhang et al. (2017) Dakun Zhang, Jungi Kim, Josep Crego, and Jean Senellart. 2017.  Boosting neural machine translation.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 271–276, Taipei, Taiwan. Asian Federation of Natural Language Processing.
  * Zhu et al. (2018) Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. 2018.  Texygen: A benchmarking platform for text generation models.  In _The 41st international ACM SIGIR conference on research & development in information retrieval_, pages 1097–1100.
  * Zipf (1936) George Kingsley Zipf. 1936.  _The Psychobiology Of Language_.  Routledge.

##  Appendix A Length normalization details

As mentioned in Section 4.1, these simple metrics have a dependency on the
length of the document, which is undesirable. Therefore, we normalize them by
dividing by their minimum possible value for a document of that length, which
is achieved on the uniform distribution. (The maximizing value, achieved by
the one-hot distribution, grows very quickly only seemed to add noise.)

###  A.1 Moment

justification=Centering

(a) Distribution of the fourth moment score on character 7-grams (found to be
the most effective for Bread-Repeat) on relatively clean samples of seven
languages, as a function of document length.

(b) The moment of the uniform distribution (red) and the adjusted uniform
distribution (yellow), where the latter simply interpolates between the number
of n-grams in a document and a max-ngram value of 5000

(c) Moment score normalized by the uniform moment. It is apparent that the
score is still length-dependent.

(d) Moment score normalized by the adjusted uniform moment. The length
dependency is much less.

Figure 4: Length normalization for the moment score

The distribution of moment scores on a sample of filtered, web-mined text
across a variety of languages333Equal mix of Arabic, English, Finnish, German,
Russian, Swahili, and Turkish can be seen in Figure 4(a). There is a clear
lower bound on this distribution, which corresponds to a uniform token
distribution. In Figure 4(b), the distribution is plotted alongside the score
on the uniform distribution (in red) and in Figure 4(c), the moment scores are
shown when normalized by the uniform distribution. It is clear that this is a
poor fit for longer documents, where the uniform distribution is more
unlikely, and indeed (in the case of a finite alphabet) impossible. Therefore,
we introduce an asymptote on the length of the document. For a document with
true length $n$, we instead calculate the uniform distribution moment on a
scaled length $\tilde{n}=\frac{n*\alpha}{n+\alpha}$, for some asymptote
$\alpha$. The yellow line in Figure 4(b) shows the uniform distribution on
$\tilde{n}$ with an asymptote of $\alpha=5000$, and Figure 4(d) demonstrates
that after dividing by this, the length dependency, at least when it comes to
the lower bound, has nicely flattened out.

###  A.2 Zipfianness

We normalize the Zipfianness score in the same way as the moment score, namely
by the score on the uniform distribution, with some asymptote parameter
$\alpha$.

##  Appendix B Grid Search

Each metric is dependent on the parameters used to smooth and nonlinearize the
frequency distribution (Section 4). Furthermore, in order to use such a metric
as a classifier for whether text is noisy or not, an appropriate threshold is
needed as the decision boundary. Therefore, for each metric, we carry out a
grid search over its possible hyperparameters. We split the Bread dataset into
a 50/50 tune/test split, and perform the grid search on the tune split. 444A
train split per se is not necessary, as we are not training any models. The
hyperparameter ranges initially explored were as follows:

Grid Search 1:

  * •

ngrams: we explore every contiguous combination of ngrams from character
2-grams to character 10-grams. We also explore token 1-grams and 2-grams, and
combinations of token 2-grams with character 5- and 6-grams, as in ChrF++.

  * •

$\epsilon$ values: we cover the range of [0, 0.01]

  * •

$k$ values: we cover the range of [2, 1024], as well as no top-k filtering

  * •

smoothing: we cover the range of [0, 2].

  * •

nonlinearities: These vary by method and are described along with each method.

However, given the small size of the tuning metric, this led to severe
overfitting. Based on analysis of which parameters were or were not very
important, we re-did the final, simpler grid search:

Grid Search 2 (constrained):

  * •

ngrams: we explored only sets of one to two ngram values at once, for instance
a mixture of 4-grams and 5-grams, but not larger sets like in the first
gridsearch. For multiple-ngram settings we looked at contiguous lengths as
well as skip-2 lengths. We explored character 1-grams to character 10-grams.

  * •

$\epsilon$ values: we did not do epsilon truncation.

  * •

$k$ values: we did not perform top-k filtering

  * •

smoothing: we only explored 0 and 1.

  * •

nonlinearities: We limited ourselves to $x^{1.5},x^{2},x^{3}$ for the moment,
and $|x-y|^{2},\log(|x-y|),\log^{2}(|x-y|),\textrm{JSD(x, y)}$ for
Zipfianness.

We optimized the grid search with the F1 metric. The choice of the
optimization metric is inherently dependent on the data balance, and a one-
size-fits-all solution is not possible; as such, though this is the metric
explored in this paper, variants of the scores optimized for different metrics
are open-sourced (See Section 6).

##  Appendix C Dataset Classes and Examples

Several examples of documents annotated with different classes from the Bread
dataset are given in Table 2.

Class | Description | Example
---|---|---
OK | natural text | Alokba den Sangremer Sensaksem | Tir Yimyim
|  | By nungsang on November 28, 2017 Comments Off on Alokba den Sangremer Sensaksem
|  | Sangremer : Alokba, nenok ashiakang kijong tepenjem kibong, Okolai nabo tulura ta
|  | meteta lir, saka nü kinungtsü indangang junga memetet. La kechi inyaker-aka?
|  | Tenünga shiba aka?
|  | Alokba : Oko, Labo mapangshia polashia tzüwa awaba dak alaka kecha balaka
|  | meinyakerako, la tenünga Tzüwala, süra ner tantsüa kechi inyaker?
|  | Kipirde basylan türkmen migrantlar
|  | Türk polisiýasy we migrant.
|  | Kipriň demirgazyk böleginiň metbugatynda soňky wagtlarda türkmen migrantlary
|  | barada köp maglumat çykyp başlady. Diňe soňky birnäçe günüň dowamynda ol ýerde
|  | birnäçe türkmen zähmet migrantlarynyň ogurlykda aýyplanyp, suda çekilip, soňra-da
|  | wagtlaýynça tussag edilendigi habar berilýär.
|  | Belli bolşy ýaly Türkmenistan garaşsyzlygyny alandan soň Türkiýe türkmen zähmet
|  | migrantlarynyň esasy ýykgyn edýän ýurtlarynyň birine öwrüldi. Türkiýedäki türkmen
|  | zähmet migrantlary barasynda türk metbugatynda yzygiderli maglumatlar çap edilýär.
|  | Ýöne indi Türkiýeden Kipriň demirgazyk bölegine gidip işleýän türkmenistanly zähmet
|  | migrantlary barada hem metbugatda çap edilýän maglumatlar köpelýär.
REP | repetitive | Shabir May 13, 2019 at 8:24 PM
| boilerplate | Shabir May 13, 2019 at 8:27 PM
|  | Shabir May 13, 2019 at 8:28 PM
|  | Do visit the site Eduassam jobs in Assam
|  | tridip May 31, 2019 at 8:24 PM
|  | golam June 12, 2019 at 10:48 PM
|  | 3.6 miles 18° 2020-01-13 12:16:54
|  | 3.7 miles 181° 2020-01-18 14:04:11
|  | 3.7 miles 181° 2020-01-19 19:29:48
|  | 3.8 miles 235° 2020-01-20 19:43:23
|  | Stations qui ont entendu WA1PLE-13 directement par radio –
|  | 2020-012019-122019-112019-102019-092019-082019-07
|  | 1 2020-01-14 03:19:07 2020-01-14 03:19:07 FN42JD >
|  | FN31ST 67.3 miles 250° 2020-01-14 03:19:07
|  | 54 2020-01-09 00:45:56 2020-01-19 06:52:58 FN42JD >
|  | FN42BF 32.4 miles 282° 2020-01-19 06:52:58
|  | 1 2020-01-15 01:20:00 2020-01-15 01:20:00 FN42JD >
|  | FN33TA 84.8 miles 317° 2020-01-15 01:20:00
BOIL | boilerplate | jasa service rolling door murah: jasa service kunci rolling
| but not | murah jakarta selatan,utara,pusat,slipi,sunter, tangerang.
| repeating | jasa service kunci rolling murah jakarta selatan,utara,pusat,slipi,sunter, tangerang.
|  | Diposting oleh ardicom di 18.53
|  | E5500/6500 68" Cabinet 4U Rack Mount Kit – Sun Parts from AnySystem.com.
|  | X9674A 595-5540 For pricing and availability, please call 201-445-3122
|  | or email<EMAIL_ADDRESS>.
|  | AnySystem - Home / X9674A 595-5540 E5500/6500 68" Cabinet 4U Rack Mount Kit
|  | – Sun Parts E5500/6500 68" Cabinet 4U Rack Mount Kit – Sun Parts from AnySystem.com.
Table 2: Bread Dataset classes and corresponding examples. Note that some
examples are excerpts from longer documents.

##  Appendix D Zipf Approximation via Random Gradient Descent

We initially calculated the empirical Zipf distribution from a linguistically
diverse set of data. However, this was cumbersome to deal with, since we
needed a value for every n-gram length and for every n-gram index, leading to
a 20x10000 table. Although the approximation of $f_{r}\propto\frac{1}{r^{b}}$,
for the 1-indexed rank of a token $r$ and some exponent $b$, is an ok
approximation, it is known to be fairly poor near the edges of the
distribution. Therefore, we used the following algorithm to determine a better
approximation, which we call Random Gradient Descent (RGD). The basic approach
is to perturb a point randomly until the loss function improves, and then
follow that direction in the parameter space until the loss stops decreasing,
and alternate doing these two steps until convergence. In pseudocode, this
algorithm looks like this:

⬇

def rgd(initial_args, loss_fn,

lr=0.01,

branch_n=10,

max_steps=10000,

max_attempts=10):

total_steps = 0

best_args = initial_args.copy()

n_failed = 0

cur_loss = loss_fn(best_args)

initial_loss = cur_loss

it = 0

while True:

it += 1

if total_steps >= max_steps: break

total_steps += branch_n

branch, branch_grad, branch_loss =

get_best_branch(best_args, loss_fn,

lr, branch_n)

if branch is None:

# This means that no branch

# improved on the best args.

# As a result, there is no

# gradient to follow.

n_failed += 1

if max_attempts

and n_failed >= max_attempts:

break

continue

cur_loss = branch_loss

n_failed = 0

best_args, follow_steps, follow_loss =

follow_grad(branch, branch_grad,

loss_fn)

total_steps += follow_steps

cur_loss = follow_loss

return best_args, cur_loss, total_steps

def get_best_branch(args, loss_fn,

lr, branch_n):

"""Look␣at␣branch_n␣random␣points

␣␣around␣args.␣Return␣the␣one␣with

␣␣the␣lowest␣loss,␣and␣if␣none␣of␣them

␣␣decreases␣the␣loss,␣return␣None’s.

␣␣"""

cur_loss = loss_fn(args)

pool_args = [(args, lr, loss_fn)

for _ in range(branch_n)]

with Pool() as p:

result =

p.map(eval_branch, pool_args)

branches, losses, grads = zip(*result)

best_loss = min(losses)

if best_loss >= cur_loss:

return None, None, None

i = losses.index(best_loss)

return branches[i], grads[i], best_loss

def follow_grad(args, grad, loss_fn,

max_flat=20):

"""Follow␣the␣gradient␣grad

␣␣until␣the␣loss␣stops␣improving.

␣␣Guaranteed␣never␣to␣make␣the

␣␣loss␣worse;␣might␣not␣change␣it.

␣␣"""

cur_loss = loss_fn(args)

initial_loss = cur_loss

best_args = args.copy()

n_flat = 0

total_steps = 0

while True:

new_args = take_step(best_args, grad)

new_loss = loss_fn(new_args)

if new_loss > cur_loss: break

elif new_loss == cur_loss:

n_flat += 1

if n_flat >= max_flat:

break

elif new_loss < cur_loss:

total_steps += 1 + n_flat

n_flat = 0

best_args = new_args.copy()

cur_loss = new_loss

return best_args, total_steps, cur_loss

The literature is certainly rich with better and subtler ways to find a good
approximation, but this method yielded an approximation that performed as well
as the empirical Zipf distribution with our methods. The approximation we
found with this method, and which we used in the main paper, is as follows,
for the $r$th most common character n-grams of length $n$ :

$\displaystyle b$ $\displaystyle=6.809*(r+2.768)^{-1.487}+0.527$
$\displaystyle s$ $\displaystyle=0.107*(n+12.0147)^{-12.654}+0.0139$
$\displaystyle f_{r}^{n}$ $\displaystyle=s\frac{1}{r^{b}}$

score | n | Tune | Test | $\alpha$ | nl | $\lambda$
---|---|---|---|---|---|---
TTR | 1 | 82.6 | 82.0 | NA | NA | NA
TTR | 2 | 82.8 | 82.4 | NA | NA | NA
TTR | 3 | 83.9 | 83.4 | NA | NA | NA
TTR | 4 | 86.3 | 85.1 | NA | NA | NA
TTR | 5 | 87.9 | 87.5 | NA | NA | NA
TTR | 6 | 89.4 | 89.2 | NA | NA | NA
TTR | 7 | 90.8 | 90.2 | NA | NA | NA
TTR | 8 | 91.8 | 90.4 | NA | NA | NA
TTR | 9 | 92.4 | 90.7 | NA | NA | NA
TTR | 10 | 92.5 | 90.1 | NA | NA | NA
mmt. | 1 | 83.3 | 82.9 | $\infty$ | $x^{1.5}$ | 1
mmt. | 2 | 84.4 | 84.6 | 2k | $x^{1.5}$ | 0
mmt. | 3 | 87.4 | 88.0 | 2k | $x^{1.5}$ | 0
mmt. | 4 | 92.3 | 91.7 | 2k | $x^{1.5}$ | 1
mmt. | 5 | 95.2 | 93.7 | 2k | $x^{1.5}$ | 0
mmt. | 6 | 95.8 | 94.9 | 2k | $x^{1.5}$ | 0
mmt. | 7 | 95.8 | 94.3 | 2k | $x^{3}$ | 1
mmt. | 8 | 95.8 | 94.6 | 2k | $x^{3}$ | 1
mmt. | 9 | 95.4 | 94.7 | 2k | $x^{3}$ | 1
mmt. | 10 | 95.1 | 94.5 | 5k | $x^{2}$ | 0
Zipf | 1 | 83.1 | 82.2 | 2k | $\log(x)$ | 1
Zipf | 2 | 84.7 | 84.0 | $\infty$ | $\log(x)$ | 0
Zipf | 3 | 90.1 | 89.7 | 2k | JSD | 1
Zipf | 4 | 94.7 | 93.7 | 2k | $x^{2}$ | 0
Zipf | 5 | 95.5 | 94.3 | 5k | $x^{2}$ | 0
Zipf | 6 | 94.5 | 93.4 | $\infty$ | $x^{2}$ | 0
Zipf | 7 | 93.5 | 92.8 | 2k | $x^{2}$ | 0
Zipf | 8 | 92.7 | 92.3 | 2k | $x^{2}$ | 0
Zipf | 9 | 91.8 | 91.3 | 2k | $x^{2}$ | 0
Zipf | 10 | 91.2 | 90.7 | 2k | $x^{2}$ | 0
Table 3: Eval on Bread-Repeat

score | n | Tune | Test | $\alpha$ | nl | $\lambda$
---|---|---|---|---|---|---
TTR | 1 | 70.7 | 70.3 | NA | NA | NA
TTR | 2 | 70.8 | 70.5 | NA | NA | NA
TTR | 3 | 71.6 | 71.3 | NA | NA | NA
TTR | 4 | 73.6 | 72.8 | NA | NA | NA
TTR | 5 | 75.2 | 74.8 | NA | NA | NA
TTR | 6 | 77.3 | 76.7 | NA | NA | NA
TTR | 7 | 79.0 | 77.7 | NA | NA | NA
TTR | 8 | 80.6 | 79.1 | NA | NA | NA
TTR | 9 | 81.6 | 79.7 | NA | NA | NA
TTR | 10 | 81.9 | 79.6 | NA | NA | NA
mmt. | 1 | 71.3 | 49.5 | $\infty$ | $x^{1.5}$ | 1
mmt. | 2 | 72.7 | 56.4 | 2k | $x^{1.5}$ | 0
mmt. | 3 | 75.4 | 58.5 | 2k | $x^{1.5}$ | 0
mmt. | 4 | 81.2 | 57.7 | 2k | $x^{1.5}$ | 1
mmt. | 5 | 86.2 | 66.9 | 2k | $x^{1.5}$ | 1
mmt. | 6 | 88.0 | 79.6 | 2k | $x^{2}$ | 1
mmt. | 7 | 88.0 | 87.6 | 2k | $x^{2}$ | 0
mmt. | 8 | 88.3 | 87.9 | 2k | $x^{2}$ | 0
mmt. | 9 | 88.1 | 87.2 | 2k | $x^{2}$ | 0
mmt. | 10 | 87.5 | 64.1 | 5k | $x^{3}$ | 1
Zipf | 1 | 71.0 | 61.3 | 2k | $\log(x)$ | 1
Zipf | 2 | 73.0 | 72.4 | $\infty$ | $\log(x)$ | 0
Zipf | 3 | 78.6 | 48.7 | 2k | JSD | 1
Zipf | 4 | 86.2 | 85.5 | 2k | $x^{2}$ | 0
Zipf | 5 | 86.0 | 85.4 | 2k | $x^{2}$ | 0
Zipf | 6 | 84.2 | 84.4 | 2k | $x^{2}$ | 0
Zipf | 7 | 82.5 | 82.4 | 2k | $x^{2}$ | 0
Zipf | 8 | 81.4 | 81.2 | 2k | $x^{2}$ | 0
Zipf | 9 | 80.1 | 79.8 | 2k | $x^{2}$ | 0
Zipf | 10 | 80.0 | 72.0 | $\infty$ | $\log(x)$ | 1
Table 4: Eval on Bread-Noisy

Table 5: F1 and Parameters of the scores that maximized the tune F1 on Bread-
Repeat and Bread-Noisy, for all combinations of character n-gram length and
score type. The parameters in question are the length-normalization asymptote
$\alpha$, the nonlinearity nl, and the Laplace smoothing parameter $\lambda$.
Perhaps the most interesting thing to note is when the tune/test F1 scores as
a function of ngram size: for the two metrics that only detect repetition (TTR
and Moment), larger ngrams are generally better, whereas for Zipfianness,
utility peaks around 5.


# Towards Task-Compatible Compressible Representations

###### Abstract

We identify an issue in multi-task learnable compression, in which a
representation learned for one task does not positively contribute to the
rate-distortion performance of a different task as much as expected, given the
estimated amount of information available in it. We interpret this issue using
the predictive $\mathcal{V}$-information framework. In learnable scalable
coding, previous work increased the utilization of side-information for input
reconstruction by also rewarding input reconstruction when learning this
shared representation. We evaluate the impact of this idea in the context of
input reconstruction more rigorously and extended it to other computer vision
tasks. We perform experiments using representations trained for object
detection on COCO 2017 and depth estimation on the Cityscapes dataset, and use
them to assist in image reconstruction and semantic segmentation tasks. The
results show considerable improvements in the rate-distortion performance of
the assisted tasks. Moreover, using the proposed representations, the
performance of the base tasks are also improved. Results suggest that the
proposed method induces simpler representations that are more compatible with
downstream processes.

Index Terms—  learnable compression, representation learning, scalable coding,
predictive $\mathcal{V}$-information

##  1 Introduction

Learnable compression methods often rely on the information bottleneck
framework [1], in which a constrained probability distribution is enforced on
an intermediate representation as it is fitted to perform a predictive task.
The resulting probability model can be used to efficiently code this
representation. In scalable coding for humans and machines [2], a compressible
representation from a computer vision task is used as side information to
assist in a reconstruction task. As an efficient representation is learned for
a particular task, there is the possibility that the relevant information
present in it cannot be fully extracted by a different process. This
phenomenon is usually referred to as co-adaptation in the transfer learning
literature [3, 4]. From an information theory point of view, the framework of
predictive $\mathcal{V}$-information [5] can also be used to interpret this
issue more formally.

In this work, we evaluate the ability of the technique proposed by [6] to
induce representations that are more compatible with secondary tasks. By
adding an auxiliary reconstruction task to the rate-distortion formulation, we
create representations that not only outperform in rate-distortion performance
of secondary tasks, but also have better rate-distortion performance on the
base task. We perform our analysis in the context of learnable scalable
coding, where a task uses a learned representation for a different task as
side-information in addition to its own representation. Current approaches for
scalable coding [2, 7] are limited in the amount of information re-utilized
from their shared representations. We provide theoretical understanding and
perform experiments to show that comparable rate-distortion performance can be
achieved on base tasks while the resulting representations still perform
effectively on secondary tasks.

##  2 Related Work

Learnable lossy compression models [8, 9, 10, 11] are often formulated as
variational autoencoders (VAEs) [12], in which a parameterized probability
distribution is fitted to the latent representation. As per the information
bottleneck framework [1], the entropy of this probability distribution is
constrained by a Lagrange multiplier, and the system is optimized to both fit
the latent representation to a probability distribution and minimize the task
performance using this representation.

To effectively encode these latent representations, the probability model is
designed to infer on a group of elements conditioned on a subset of previously
observed elements. The latent representation is then quantized and encoded
using the probability model to produce a bitstream at a resulting rate. In
these methods, the loss of information arises from the quantization of the
latent representation and from the analysis transform, as shown by the data
processing inequality [13].

Entropy models [9, 11] are developed to be used in conjunction with a lossy
encoder [14, 15]. Their architectures usually divide the dimensions of the
latent representation into groups for parallel processing. Most of these
models can use side-information as context for conditional coding. We make use
of this feature to perform experiments in which we test the performance of our
proposed methods using the scalable conditional coding from [6]. While [6]
focused on conditional and residual approaches for coding the enhancement
layer for input reconstruction, in this paper our focus is on compatibility of
base representation with secondary tasks, which may or may not be input
reconstruction. The scalable coding framework from [6] is used as the platform
for this study.

Most work on scalable learnable coding [2] considers two tasks: a computer
vision task (base task) and the image reconstruction task (enhancement task).
It is often assumed that the information available in the latent
representation of the computer vision task is a subset of the information
required for image reconstruction. As such, different methods have been
proposed to complement the information available in the latent representation
of the computer vision task for the reconstruction task. To increase the
amount of utilization of this base representation, the work in [6] proposed to
train the latent representation to reconstruct the input. In this work, we
provide theoretical analysis, extend this idea to non-reconstruction tasks,
and evaluate this approach.

Predictive $\mathcal{V}$-information [5] extends the concepts of Shannon’s
information theory to consider the computational limitations. These concepts
explain situations in which computation can increase the amount of information
perceived, which would seem to violate the classical data processing
inequality [13]. We use them to demonstrate how our representations can be
compatible with other task models designed to work on the original input
space.

##  3 Proposed Method

Fig. 1: Architecture overview. The green lines denote the scalable approach,
and the red line denotes a direct approach where the secondary task only has
access to the base representation. The dotted lines mean that gradients do not
flow past that edge.

We define the problem in terms of predictive $\mathcal{V}$-information and
reframe the solution presented in [6] accordingly. After a brief theoretical
analysis, we describe our model architecture and define the scalable learnable
compression setup.

###  3.1 Problem Formulation

A learnable compressor for input $X$ and target $Z$ defines the Markov chain
$X\to Y\to\hat{Z}$, where $\hat{Z}$ tries to approximate $Z$. Let
$\mathcal{F}$ be the set of all analysis transforms such that
$\mathbf{f}\in\mathcal{F};\mathbf{f}:\mathcal{X}\to\mathcal{Y};\mathcal{Y}\subseteq\mathbb{Z}^{M};M\in\mathbb{N}^{+}.$
Also, let $\mathcal{G}$ be the set of all attainable111Given the architecture,
complexity constraints, etc. synthesis transforms, with
$\mathbf{g}\in\mathcal{G};\mathbf{g}:\mathcal{Y}\to\mathcal{Z}$. Using the
$\mathcal{V}$-information [5] framework, the objective of the learnable
compressor can be expressed as:

$\displaystyle\sup_{\mathbf{f}\in\mathcal{F}}I_{\mathcal{V}}(\mathbf{f}(X)\to
Z)$
$\displaystyle=\sup_{\mathbf{f}\in\mathcal{F}}\left[H_{\mathcal{V}}(Z|\emptyset)-H_{\mathcal{V}}(Z|\mathbf{f}(X))\right],$

where $I_{\mathcal{V}}$ is the predictive $\mathcal{V}$-information and
$H_{\mathcal{V}}(\cdot|\cdot)$ is the predictive conditional
$\mathcal{V}$-entropy, defined as:

$\displaystyle
H_{\mathcal{V}}(Z|Y)=\inf_{h\in\mathcal{V}}\mathbb{E}_{\mathbf{z},\mathbf{y}\sim
Z,Y}\left[-\log h[\mathbf{y}](\mathbf{z})\right],$

where:

$\displaystyle\mathcal{V}\subset\\{h:\mathbf{y}\to\mathcal{P}(\mathcal{Z};\mathbf{g}(\mathbf{y})),\mathbf{y}\in\mathcal{Y};\emptyset\to
P(\mathcal{Z})|\mathbf{g}\in\mathcal{G}\\}$

is a set of predictive models that can be attained by the choice of model and
optimization algorithm. $\mathcal{P}(\mathcal{Z};\mathbf{g}(\mathbf{y}))$
denotes the set of all probability measures on $\mathcal{Z}$, parameterized by
$\mathbf{g}(\mathbf{y})$. Thus, in this analysis, attaining the mutual
information $I(X;Z)$ is limited by the expressiveness of $\mathcal{G}$ and
$\mathcal{V}$, but not $\mathcal{F}$, since it includes all analysis
transforms.

###  3.2 Task-Compatible Representations

Let
$\mathbf{f}^{*}_{b}=\operatorname*{arg\,max}_{\mathbf{f}\in\mathcal{F}}I_{\mathcal{V}_{b}}(\mathbf{f}(X)\to
Z_{b})$ be the best analysis transform for the base task $Z_{b}$ given
$\mathcal{V}_{b}$, and let:

$\displaystyle\mathcal{F}^{*}_{b}=\left\\{\mathbf{f}\in\mathcal{F}:I_{\mathcal{V}_{b}}(\mathbf{f}(X)\to
Z_{b})=I_{\mathcal{V}_{b}}(\mathbf{f}^{*}_{b}(X)\to Z_{b})\right\\}$

be the set of functions that achieve the best predictive
$\mathcal{V}$-information for that task. For the secondary task $Z_{e}$ and a
set of attainable synthesis transforms $\mathcal{G}_{e}$ with a corresponding
predictive family $\mathcal{V}_{e}$, we have that:

$\displaystyle I_{\mathcal{V}_{e}}(\mathbf{f}^{*}_{b}(X)\to
Z_{e})\leq\operatorname*{arg\,max}_{\mathbf{f}\in\mathcal{F}^{*}_{b}}I_{\mathcal{V}_{e}}(\mathbf{f}(X)\to
Z_{e}).$ (1)

Thus, it would be ideal to propose a different analysis transform
$\hat{\mathbf{f}}_{b}\in\mathcal{F}^{*}_{b}$ that achieves a higher predictive
$\mathcal{V}$-information on task $Z_{e}$ while retaining the same performance
on task $Z_{b}$. To induce this, we propose the following objective:

$\displaystyle\sup_{\mathbf{f}\in\mathcal{F}}\left\\{I_{\mathcal{V}_{b}}(\mathbf{f}(X)\to
Z_{b})+\beta I_{\mathcal{V}_{a}}(\mathbf{f}(X)\to Z_{a})\right\\},$ (2)

where $Z_{a}$ is an auxiliary task, $\beta$ is a sufficiently small positive
scalar, and $\mathcal{V}_{a}$ is a predictive set given by the set of
synthesis transforms $\mathcal{G}_{a}$. By setting $Z_{a}=X$, we add a small
reward on the capacity of $\mathbf{f}$ to reconstruct the input using a simple
transform, preventing the co-adaptation or specialization of $Y$ to the main
task $Z_{b}$. The choice of reconstruction as a task and a simple synthesis
transform ensures that an approximation of the original input can be recovered
by other tasks. This seems to be a good general choice, since task models are
often designed to work on the original input space and can be trained in an
unsupervised manner. We design the architecture defining $\mathcal{G}_{a}$ to
be subsumed by the synthesis transforms $\mathcal{G}_{e}$ of the secondary
task, ensuring that the model has enough expressive power to reconstruct the
input and perform the task, if necessary.

A small $\beta$ must be chosen to avoid driving the new objective too far away
from the original performance on the primary task. However, considering that
the original objective is already a combination of tasks, namely the task
objective and the entropy minimization objective, it could be beneficial to
use the proposed objective in single-task scenarios. The proposed objective
could then prevent the co-adaptation between the representation and the
entropy or task models.

###  3.3 Model Architecture

As analysis and synthesis transforms for the vision problem space, we use
convolutional neural networks (CNN), consisting of scaling operations
interleaved with stacks of residual bottleneck blocks [16]. The structure of
such blocks is the same as [11] but compared to the overall architecture,
there are no attention blocks. As we scale down the spatial resolution we
increase the number of channels in the analysis transform and do the inverse
for the synthesis transform using transposed convolutions. We have 4 scaling
operations, each by a factor of 2. We use Exponential Linear Units (ELU) as
activation functions. To perform a concrete task, we connect a task-
appropriate neural network to the synthesis transform.

As an entropy model, we rely on the auto-regressive model of [9]. The model
leverages masked convolutions to enforce the necessary context constraints. At
each step, it processes all channels for a particular spatial dimension. The
context corresponds to all dimensions of the previous spatial locations within
the receptive field of the CNN. The learnable compression model of [9]
generates a hyper-prior that is used as side-information by the entropy model.
We use this mechanism to inject the side-information from the primary task, as
to conditionally code the representation of the secondary task. The
representation of the primary task is processed by a ResNet and concatenated
with the context to predict the means and standard deviations of a
multivariate normal distribution assigned to the secondary representation. The
primary task is encoded without any hyper-prior or side-information.

Fig. 1 shows a diagram of this
architecture.222https://github.com/adeandrade/research A direct approach to
perform the secondary task is included in which we train the task using the
shared representations as input, without a dedicated channel. This
architecture will be used to further evaluate the proposed method.

###  3.4 Coding Fidelity

The quantization of the latent representation during training is simulated in
the proposed model of [9] using additive uniform noise
$\mathcal{U}(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$. This technique is used
to allow gradients to back-propagate through the representation. However, it
produces small discrepancies between the decoded and original representations,
which the synthesis transform must learn to ignore. In some settings, these
differences penalize the performance of the task during test time. To avoid
this situation, we instead replace the round operations with quantization and
straight-through gradients [17] where quantization gradient is set to the
identity function. The symbols to be encoded are then computed as
$\lfloor\hat{y}-\mu\rceil;\hat{y}=\lfloor y\rceil$, and the decoding process
performs $\lfloor\lfloor\hat{y}-\mu\rceil+\mu\rceil$, which recovers
$\hat{y}$. We use $\hat{y}$ as input to the entropy model, synthesis
transforms, and the rate function, during both training and test time. This
ensures that the entropy model produces the same results when using the
original representation or generating it auto-regressively. Accurate rate
measurements can then be performed without encoding the representation.

###  3.5 Scalable Compression

We employ the information bottleneck [1] to produce intermediate lossy
representations $Y_{b}$ and $Y_{e}$ for tasks $Z_{b}$ and $Z_{e}$
respectively. In scalable compression, we refer to the shared representation
$Y_{b}$ as belonging to the base task and the dedicated representation $Y_{e}$
as the enhancement task. As presented in [6], we add a small reconstruction
reward to the rate-distortion Lagrange minimization formulation of the base
loss, such that:

$\displaystyle\mathcal{L}_{b}(\psi_{b},\phi_{b},\theta_{b},\theta_{a})=\lambda_{b}\mathbb{E}[d_{b}(\hat{Z}_{b},Z_{b})]+R_{b}+\beta\mathbb{E}[\|{\hat{X}\shortminus
X\|}];$ $\displaystyle
Y_{b}=\mathbf{f}_{b}(X;\psi_{b}),\hat{Z}_{b}=\mathbf{g}_{b}(\hat{Y}_{b};\theta_{b}),\hat{X}=\mathbf{g}_{a}(\hat{Y}_{b};\theta_{a}),$
$\displaystyle R_{b}=\hat{h}(\hat{Y}_{b};\phi_{b}),$ (3)

where $\hat{h}(\cdot;\phi_{b})$ is an entropy estimate parameterized by
$\phi_{b}$, $d_{b}(\cdot,\cdot)$ is the base task loss. $\lambda_{b}$ and
$\beta$ are hyper-parameters. The $\lambda$ hyper-parameter controls the rate-
distortion trade-off. For the enhancement task, we use the traditional rate-
distortion loss function:

$\displaystyle\mathcal{L}_{e}(\psi_{e},\phi_{e})=\lambda_{e}\mathbb{E}[d_{e}(\hat{Z}_{e},Z_{e})]+\hat{h}(\hat{Y}_{e}|\hat{Y}_{b};\phi_{e});$
$\displaystyle\hat{Y}_{e}=\mathbf{f}_{e}(X;\psi_{e}),\hat{Z}_{e}=\mathbf{g}_{e}(\hat{Y}_{e};\theta_{e}),$
(4)

where $\hat{h}(\cdot|\cdot;\phi_{e})$ is the conditional entropy estimate,
parameterized by $\phi_{e}$. During training, either
$\mathbf{f}_{b}(\cdot;\psi_{b})$ remains frozen, or the gradients from the
enhancement loss do not flow to it.

##  4 Experiments

(a) Direct with object detection

(b) Direct with depth estimation

(c) Scalable with object detection

(d) Scalable with depth side-information

(e) Object detection

(f) Depth estimation

Fig. 2: Rate-distortion performance of base representations on image
reconstruction (a)-(d) and base tasks (e)-(f). Left: object detection on COCO
2017; Right: depth estimation on Cityscapes. “Direct” means reconstructing the
input from the base representation directly, without the dedicated channel
(see Fig. 1). “Scalable” means coding reconstruction representation
conditional on the base representation; in this case, the BPP reported is the
sum of both representations. The “Standalone” method does not use side-
information. The lines marked “Uncompressed” correspond to the best task
performance obtained with a very large $\lambda_{b}=1,000$, amongst the
baseline and proposed methods. PSNR units are in decibels (dB).

We perform two different sets of experiments that evaluate the proposed method
under different settings. In the first set of experiments, we evaluate the
compatibility of compressible learned representations for base tasks against
the input reconstruction task. We perform experiments on the COCO 2017 dataset
[18] using object detection as the base task, and on the Cityspaces dataset
[19], using depth estimation as the base task. In the second set of
experiments, we evaluate the compatibility of a representation learned for
depth estimation as the base task, against semantic segmentation as the
secondary task, on Cityscapes. We evaluate the rate-distortion performance of
the secondary task in a scalable setting, where we conditionally code the
secondary representation using the base representation as side-information.
The baseline against which we compare has the same proposed architecture and
setup, but with $\beta=0$ in (2)-(3), which is the typical choice for scalable
codecs [2, 7]. Hence, the comparison against this baseline assesses whether
the additional term with $\beta>0$ improves task compatibility of learned
representations. In practice, $\mathbf{g}_{a}(\cdot;\theta_{a})$ is removed
from the architecture.

We first train the shared representation on the base task with different
values of $\lambda_{b}$, then we choose a representation from each method
producing similar rates and use it to generate side-information for the
secondary task. A “standalone” method is included in which the base
representation is zeroed-out and the entropy model is fine-tuned on a frozen
fully-trained analysis transform from the proposed method.

The COCO 2017 dataset consists of 123,287 domain-agnostic images for object
detection and segmentation [18]. We use Faster R-CNN [20] for object detection
with ResNet-50 [16] as the back-end. The Cityscapes datasets consists of
images of urban scenes. For depth estimation, LRASPP is used with MobileNetV3
as the back-end [21]. DeepLabV3 [22] is used for segmentation, with ResNet-50
as back-end.

###  4.1 Setup

We set the dimensionality of the feature space as $M=192$. Our proposed method
uses $\beta=0.1$. We train using Adam with a fixed learning rate of $1\times
10^{-4}$, and early-stopping with a patience of 10-50 epochs depending on the
task, and a maximum of 1,000 epochs. As data augmentation, we apply random
horizontal flips and color jittering. Since the input of Cityscapes has a high
resolution, we downscale it by a factor of 2 before processing it and upsample
back the resulting predictions before evaluating their performance, ensuring
we are still operating on the original problem.

To train the reconstruction tasks, we use the root mean squared error (RMSE)
as the distortion function. We compute and report the bits-per-pixel (BPP)
using the rate given by the entropy estimates. To speed up the computation of
the rate-distortion curve, we train a model for low-compression (highest
$\lambda_{b}$ or $\lambda_{e}$) and use its parameters as initialization for
the models producing the rest of the curve.

###  4.2 Input Reconstruction as the Secondary Task

In this set of experiments, we train representations on the base computer
vision tasks and evaluate their performance on image reconstruction. We
evaluate the compatibility of these representations in two ways. In the first
approach, we train a reconstruction model using the representations generated
as immutable input. Since the secondary task is reconstruction, this method
highlights how much information regarding the input can be extracted from
these representations. In the second approach, we use the representations as
side-information to conditionally code a dedicated secondary representation
used for reconstruction. This approach shows how compatible the base
representation is with the representation trained for image reconstruction.

We generate rate-distortion curves for the base task using our approach and
the previously described baseline. For each method, we choose one of the
models producing a point on the rate-distortion curve as the feature generator
for the scalable image reconstruction approach. We choose points with similar
BPP values between the two methods.

Fig. 2 shows the results obtained. For object detection on COCO 2017, the
advantage of the proposed method over the baseline is obvious in Fig. 2(a),
but the BD-rate [23] could not be computed as the curves do not have an
overlap on the vertical axis. The BD-rate advantage over the baseline is 10.3%
in Fig. 2(c) and 1.3% in Fig. 2(e), showing that the proposed method has a
small positive impact on the performance of the base task, while attaining
significant gains on the secondary task. For depth estimation on Cityscapes,
the proposed method achieves a significant BD-rate gains of 85.2% and 22.2% in
Figs. 2(b) and 2(d), respectively, with a BD-Rate gain of 74.8% in Fig. 2(f).
Again, an advantage on the base task is achieved together with a significant
advantage on the secondary task. As discussed previously, this improvement can
be explained by the method preventing the co-adaptation to the task and
entropy models.

The image reconstruction performance of the baseline has an interesting
behaviour where in low-rate regimes, higher peak signal-to-noise ratio (PSNR)
values can be attained. Since the baseline has no reward in creating
representations that can be easily used for secondary tasks, the level of
compatibility achieved between different representations can vary
unexpectedly.

###  4.3 Secondary Computer Vision Task

Fig. 3: Rate-distortion performance of scalable conditional coding on semantic
segmentation on Cityscapes. The BPP measurements corresponds to the sum of the
base and secondary rates. Although the distortion function
$d_{e}(\cdot,\cdot)$ used in training is the per-pixel multi-class cross-
entropy, we report the more conventional mean Intersection-over-Union (mIoU)
test metric.

To demonstrate that rewarding input reconstruction can also increase the
compatibility of the resulting representations with other tasks, we further
evaluate the proposed method in a setting where the secondary task is another
computer vision task. We employ the same model architecture used earlier on
Cityscapes, except that now the secondary task is set to semantic segmentation
rather than input reconstruction.

We run a scalable architecture, in which there is a secondary representation
dedicated to semantic segmentation, which is coded conditionally given the
base representations used for depth estimation. Fig. 3 shows the rate-
distortion performance of the proposed method compared to the baseline and
“standalone” methods on the training set. Due to the small size of the
Cityscapes dataset, there is likely some level of overfitting affecting all
three methods, which results in fairly high segmentation accuracies in terms
of mIoU. Nonetheless, the main comparison here is in terms of the required
bitrates, and we see that the proposed method achieves a solid compression
gain over the baseline, 26.2% in terms of the BD-rate. Moreover, the results
indicate that the baseline method is unable to extract any useful information
from the base representation to support conditional coding of the secondary
representation, because it achieves almost the same performance as the
“standalone” method, which does not use the base representation at all.

##  5 Conclusion

We studied how well a learned compressible representation for a given task is
able to support conditional coding of a secondary task. We demonstrated that
in a conventional learned scalable coding, extracting useful information from
the base representation is a challenge. However, if the base representation is
rewarded for supporting input reconstruction during training, it becomes
easier for a conditional codec to use this representation for the secondary
task, even if that task is not input reconstruction. One possible explanation
for this is that, due to the unsupervised nature of the input reconstruction
task, the base representation remains more generic and useful when extending
to multiple, potentially unknown, tasks.

The $\mathcal{V}$-information framework provides a possible interpretation in
terms of the increase of predictive $\mathcal{V}$-information in the base
representation $Y_{b}$ for a predictive family $\mathcal{V}_{e}$. This would
especially be the case when the auxiliary task inducing $Y_{b}$ is
sufficiently non-specific (such as input reconstruction), and
$\mathcal{V}_{a}$ is sufficiently simple, so as to reduce co-adaptation and
generalize to other tasks.

## References

  * [1] N. Tishby, F. C. N. Pereira, and W. Bialek,  “The information bottleneck method,”  CoRR, vol. physics/0004057, 2000.
  * [2] H. Choi and I. V. Bajić,  “Scalable image coding for humans and machines,”  IEEE TIP, vol. 31, pp. 2739–2754, 2022.
  * [3] J. Yosinski, J. Clune, Y. Bengio, and H. Lipson,  “How transferable are features in deep neural networks?,”  in NIPS, 2014.
  * [4] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan,  “A theory of learning from different domains,”  Machine Learning, vol. 79, no. 1-2, pp. 151–175, 2010.
  * [5] Y. Xu, S. Zhao, J. Song, R. Stewart, and S. Ermon,  “A theory of usable information under computational constraints,”  in ICLR, 2020.
  * [6] A. de Andrade, A. Harell, Y. Foroutan, and I. V. Bajić,  “Conditional and residual methods in scalable coding for humans and machines,”  in IEEE ICMEW, 2023.
  * [7] Y. Foroutan, A. Harell, A. de Andrade, and I. V. Bajić,  “Base layer efficiency in scalable human-machine coding,”  in IEEE ICIP, 2023, pp. 3299–3303.
  * [8] J. Ballé, V. Laparra, and E. P. Simoncelli,  “End-to-end optimized image compression,”  in ICLR, 2017.
  * [9] J. Ballé, D. Minnen, S. Singh, S. J. Hwang, and N. Johnston,  “Variational image compression with a scale hyperprior,”  in ICLR, 2018.
  * [10] Z. Cheng, H. Sun, M. Takeuchi, and J. Katto,  “Learned image compression with discretized gaussian mixture likelihoods and attention modules,”  in IEEE CVPR, 2020.
  * [11] D. He, Z. Yang, W. Peng, R. Ma, H. Qin, and Y. Wang,  “ELIC: efficient learned image compression with unevenly grouped space-channel contextual adaptive coding,”  in IEEE CVPR, 2022.
  * [12] D. P. Kingma and M. Welling,  “Auto-encoding variational bayes,”  in ICLR, 2014.
  * [13] T. M. Cover and J. A. Thomas,  Elements of information theory,  Wiley, 2nd edition, 2006.
  * [14] W. Jiang, J. Yang, Y. Zhai, P. Ning, F. Gao, and R. Wang,  “MLIC: multi-reference entropy model for learned image compression,”  in ACM, 2023.
  * [15] W. Jiang and R. Wang,  “MLIC++: linear complexity multi-reference entropy modeling for learned image compression,”  CoRR, vol. abs/2307.15421, 2023.
  * [16] K. He, X. Zhang, S. Ren, and J. Sun,  “Deep residual learning for image recognition,”  in IEEE CVPR, 2016.
  * [17] L. Theis, W. Shi, A. Cunningham, and F. Huszár,  “Lossy image compression with compressive autoencoders,”  in ICLR, 2017.
  * [18] T.-Y. Lin, M. Maire, S. J. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick,  “Microsoft COCO: common objects in context,”  in ECCV, 2014.
  * [19] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele,  “The Cityscapes dataset for semantic urban scene understanding,”  in IEEE CVPR, 2016.
  * [20] S. Ren, K. He, R. B. Girshick, and J. Sun,  “Faster R-CNN: towards real-time object detection with region proposal networks,”  IEEE TPAMI, vol. 39, no. 6, pp. 1137–1149, 2017.
  * [21] A. Howard, R. Pang, H. Adam, Q. V. Le, M. Sandler, B. Chen, W. Wang, L.-C. Chen, M. Tan, G. Chu, V. Vasudevan, and Y. Zhu,  “Searching for MobileNetV3,”  in IEEE ICCV, 2019.
  * [22] L.-C. Chen, G. Papandreou, F. Schroff, and H. Adam,  “Rethinking atrous convolution for semantic image segmentation,”  CoRR, vol. abs/1706.05587, 2017.
  * [23] G. Bjontegaard,  “Calculation of average PSNR differences between RD-curves,”  ITU-T SC16/Q6 VCEG-M33, 2001.