# TSTR: Target Similarity Tuning Meets the Real World

Anirudh Khatry
Priyanshu Gupta
Ananya Singha
Microsoft
Bangalore, India
Sumit Gulwani
Vu Le
Microsoft
Redmond, US
Mukul Singh
Microsoft
Delhi, India
Gust Verbruggen
Microsoft
Keerbergen, Belgium  First author

###### Abstract

Target similarity tuning (TST) is a method of selecting relevant examples in
natural language (NL) to code generation through large language models (LLMs)
to improve performance. Its goal is to adapt a sentence embedding model to
have the similarity between two NL inputs match the similarity between their
associated code outputs. In this paper, we propose different methods to apply
and improve TST in the real world. First, we replace the sentence transformer
with embeddings from a larger model, which reduces sensitivity to the language
distribution and thus provides more flexibility in synthetic generation of
examples, and we train a tiny model that transforms these embeddings to a
space where embedding similarity matches code similarity, which allows the
model to remain a black box and only requires a few matrix multiplications at
inference time. Second, we show how to efficiently select a smaller number of
training examples to train the TST model. Third, we introduce a ranking-based
evaluation for TST that does not require end-to-end code generation
experiments, which can be expensive to perform.

##  1 Introduction

Code generation from natural language utterances is an important and useful
ability of large language models (LLMs). Experienced developers can save time,
and less experienced users can use natural language to perform data
transformation tasks that they would otherwise have to carry out manually Liu
et al. (2023). Improving the code generation capabilities of LLMs is a popular
research area Wang et al. (2021).

Target similarity tuning (TST) was proposed as a method for selecting relevant
examples to exploit the in-context learning ability of LLMs and improve
performance Poesia et al. (2022). TST improves the alignment between sentence
embeddings of utterances by fine-tuning their cosine similarities to match the
similarity of their associated code snippets. Sentence-BERT Reimers and
Gurevych (2019) is used as embedding model. Especially for rare programming
languages, the model benefits from seeing relevant code (+3% for SQL versus
+16% for SMCalFlow using GPT-3).

######  Example.

Figure 1 shows an example of how TST improves over default embeddings by
teaching the model which parts of the utterance are important. The embeddings
focus heavily on the “into rows” part of the utterance (where the user might
have made a mistake). With TST, we can teach it to focus on the “delimiter”
part by focusing on the similarity between code snippets.

Figure 1: Example of a target utterance and associated code, the examples
selected by TST and by relying on default embeddings.

This paper addresses four limitations of TST when applying it in the real
world: (1) sensitivity to language, (2) inference with transformer models, (3)
dataset curation and (4) evaluation.

Limitations (1) and (2) are due to the sentence embedding model. Training
utterances and real utterances often come from different distributions, for
example, from users with different skill levels, and smaller models might be
unable to capture this variation. When hosted, third-party LLMs are used for
code generation, performing inference with transformer models might not be
possible, making TST hard to use in production.

We address both these challenges by replacing the sentence transformer with
embeddings from a hosted, third-party model and training a fully connected
neural network (FCNN) to transform the embeddings to capture the code
similarity. The large model provides stronger embeddings and the FCNN only
requires a (few) matrix-vector multiplication during inference.

Dataset curation (3) is important, as given $n$ (utterance, code) pairs, we
can sample $n(n-1)/2$ pairs to create training examples for TST, most of
consist of irrelevant code pairs. Since we care about distinguishing the best
examples, these irrelevant pairs are not desired. We address this challenge by
selecting positive and negative examples close to the important decision
boundary and create a smaller dataset that yields better performance and is
much faster to train on.

Our method proposed method of training the FCNN on top of frozen embeddings on
a relevant set of examples is called TSTR (_tastier_), where R stands for real
world.

Finally, optimizing hyperparameters of the TST model is expensive to evaluate
when LLM calls are required. We show that an evaluation based on ranking of
examples close to the decision boundary matches the end-to-end performance,
providing a cheap way to evaluate TST models.

We make the following contributions:

  * (1 + 2)

We show that training a small model on top of frozen embeddings makes TSTR
easier to train and use, and less sensitive to variations in language.

  * (3)

We show that selecting examples close to the important decision boundary
allows us to train a TST model with much fewer examples.

  * (4)

We show that ranking (train, test) utterance pairs correlates to the
performance of end-to-end code generation, providing a cheap way to evaluate
TST models.

##  2 Related Work

Code generation from natural language is a popular area of research Le et al.
(2022); Li et al. (2022). Instead of starting from scratch, fine-tuning a pre-
trained natural language understanding model to generate code is a popular
approach, for example, CodeBERT Feng et al. (2020) was trained from BERT,
CodeT5 Wang et al. (2021) was trained from T5 and Codex Chen et al. (2021) was
trained from GPT-3.

A powerful method to generate code from natural language is prompting large
language models Chen et al. (2021). As opposed to fine-tuning, this does not
require large training datasets and expensive compute. Few-shot prompting
consistently improves the performance of LLMs across a variety of tasks Brown
et al. (2020). Besides helping the model pick the correct programming language
Athiwaratkun et al. (2023) the provided few-shots can teach the model about
specific functions or parameters and contextualization.

One way of selecting relevant examples is by using sentence embeddings Liu et
al. (2021). In some cases, however, similar natural language does not
correspond to similar code, and vice versa. Synchromesh Poesia et al. (2022)
introduced target similarity tuning (TST) to address this challenge and fine-
tunes the sentence embedding similarity to match the associated code
similarity.

This work builds on the concept of TST and improves on important
implementation details for training (selecting examples and allowing synthetic
data generation), evaluating (cheap evaluation with a proxy metric) and
deploying (API call and small FCNN do not have hardware requirements) TST in
practice.

##  3 TSTR

We briefly recap TST, how that transfers to TSTR and how examples closer to
the relevant decision boundary are selected to improve training

###  3.1 TST

Given two (utterance, code) pairs $(u_{1},c_{1})$ and $(u_{2},c_{2})$, vanilla
TST fine-tunes a semantic textual similarity (STS) model $S_{m}$ to minimize

$\|S_{m}\left(u_{1},u_{2}\right)-S_{c}(c_{1},c_{2})\|$ (1)

with $S_{c}$ a similarity between code pairs. The STS model is SBERT, which
pools BERT tokens and fine-tunes pooled embeddings to capture similarity
between pairs of sentences. TST then transforms the embedding to capture
properties of utterances that make their associated code similar.

###  3.2 TST with Embeddings

We decouple the embedding from the similarity and compute

$S_{m}(u_{1},u_{2})=\cos(t_{\theta}(m(u_{1})),t_{\theta}(m(u_{2})))$ (2)

with $\cos$ the cosine similarity between vectors, $m$ a $d$-dimensional
embedding model (such as SBERT) and
$t_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d^{\prime}}$ a trainable
transformation. The parameters of $m$ are frozen. To keep $t_{\theta}$ simple,
we use a fully connected network with $\tanh$ activation.

###  3.3 Training

The training data consists of $(u_{1},u_{2},S_{c}(c_{1},c_{2}))$ triplets.
Instead of randomly sampling $(u_{1},c_{1})$ and $(u_{2},c_{2})$ pairs, we aim
to find examples close to the relevant decision boundary. That is, we care
about examples for which: (1) $S_{c}(c_{1},c_{2})$ is high, or (2)
$S_{c}(c_{1},c_{2})$ is low but $\cos(m(u_{1}),m(u_{2}))$ is high—that are
similar in the original embedding space but have dissimilar code. In other
words, we care about examples with properties that we need to learn and that
we need to unlearn. For each pair $(u_{i},c_{i})$ we therefore rank all other
$(u_{j},c_{j})$ by $S_{c}(c_{i},c_{j})$ and select the top-$\lambda_{k}$ best
ones. We then skip $\lambda_{s}$ examples to ensure that code similarity is
not too high, rank the remaining examples by $S_{c}(m(u_{i}),m(u_{j}))$ and
again select the top-$\lambda_{k}$ best ones in this new ranking.
$\lambda_{k}$ and $\lambda_{s}$ are hyper-parameters.

##  4 Evaluation Setup

This section describes the datasets, metrics, models and hyperparameters used
in our experiments.111https://github.com/microsoft/prose-
benchmarks/tree/main/TSTR

###  4.1 Datasets

We evaluate TSTR on three NL-to-code datasets across different low-resource
languages. For each language, we also report the evaluation metric and code
similarity $S_{c}$.

####  4.1.1 Power Query M

The Power Query M language (or M) is used for transforming data in Power
Query. We use the data from Khatry et al. (2023) consisting of code snippets
sourced from StackOverflow (test) and the Power Query Community
Forum222https://community.fabric.microsoft.com/t5/Power-Query/bd-p/power-bi-
services (train and test). The testing set contains 500 snippets annotated by
experts. The training set includes 8000 snippets annotated via an LLM (text-
davinci-002). We report _execution match_ and _sketch match_ , two standard
metrics for code generation Poesia et al. (2022); Singh et al. (2022).
Execution match (boolean) is determined by executing both the ground truth and
generated code snippets on a table and checking for equality. Sketch match
($\in[0,1]$) is computed as the normalized (Levenshtein) edit similarity
between the ground truth and generated code snippets after masking constants
(strings and numbers) and identifiers (column names). We use sketch match as
$S_{c}$.

####  4.1.2 SMCalFlow

SMCalFlow is a task-oriented dialogue dataset of user-agent conversations,
where each user query is annotated with a program in a domain-specific
language that facilitates a dialogue over a dataflow graph Andreas et al.
(2020). In line with previous work Poesia et al. (2022), we select the first
turn from each dialogue to define an NL-to-code task and sample 2000 training
examples (out of 40K). The test set consists of 2673 examples. We follow
Poesia et al. (2022) and use the normalized edit similarity for both
evaluation and $S_{c}$.

####  4.1.3 Bash

The nl2bash dataset consists of bash code snippets, each with an expert-
curated natural language description Lin et al. (2018). The train and test
sets contain 8090 and 606 examples, respectively. We use the _template match_
metric proposed in the original paper for both evaluation and $S_{c}$.

###  4.2 Models and Hyperparameters

We use text-embedding-ada-002 (ada) and text-davinci-003 (GPT-3) (both from
OpenAI) as the embedding and code generation models. In TSTR, we use two fully
connected layers with 512 parameters (see Section 5.2). To prevent
overfitting, we apply dropout (0.3) between the embedding and the fully
connected layer. $\lambda_{k}$ and $\lambda_{s}$ are set to 4.

###  4.3 Baselines

Across experiments, we use the following baselines for example selections with
embeddings. For each baseline, we select eight examples.

  * •

Vanilla ada and SentenceBERT embeddings.

  * •

TST Poesia et al. (2022) trained on examples selected according to our
selection strategy (Section 3.3) for one epoch. Using random examples
performed worse.

  * •

A hybrid approach with frozen SentenceBERT embeddings instead of ada (called
TSTf).

##  5 Evaluation

Table 1: TSTR performance across languages on end-to-end code generation task. We find that TST easily overfits on the language distribution of the training data, but TSTR does not.  Technique | M | SMCF | Bash
---|---|---|---
Static | 0.20 | 0.43 | 0.56
SentenceBERT | 0.53 | 0.87 | 0.65
ada | 0.54 | 0.89 | 0.67
TST | 0.52 | 0.89 | 0.63
TSTR | 0.55 | 0.90 | 0.68

We perform experiments to compare TSTR against baseline embedding retrieval
methods (5.1), we show that ranking relevant examples serves as a proxy metric
to optimize hyperparameters without LLMs (5.2), we evaluate how embeddings
from large models (ada) are more robust with respect to variations in language
(5.3), and we show the effect of selecting relevant examples to train TSTR
(5.4).

###  5.1 Performance

Table 1 shows results of TSTR and baselines, as well as a static prompt with
eight randomly selected examples. TSTR consistently performs better (+1%) over
vanilla embeddings.

Surprisingly, the original TST approach to fine tune SentenceBERT hurts
performance on M (-1%) and Bash (-2%). This may be attributed to overfitting
on the language of the training set, and not being able to relate new
variations in language to the code similarity (see Section 5.3).

###  5.2 Standalone Evaluation

We create a pairwise ranking dataset to evaluate TSTR without performing end-
to-end code generation and evaluate this approach on M.

Each test point consists of a triplet $(u_{r},u_{p},u_{n})$ where $u_{r}$ is a
reference utterance from the testing dataset, $u_{p}$ and $u_{n}$ are
candidate utterances from the training dataset, and
$S_{c}(c_{p},c_{r})>S_{c}(c_{n},c_{r})$. We consider two ways of sampling
$u_{p}$ and $u_{n}$ and thus create two testing datasets: at random ($\star$)
or close to the relevant decision boundary, similar to how the training
dataset is created ($\bullet$). We count proportion of correct pairwise
decisions.

We compare the execution match (end-to-end) and pairwise ranking evaluation
for different embedding-based example selection strategies in Figure 2.
Besides baselines, we also consider the theoretical maximum for a given
similarity using the code–code similarity.

Our ranking evaluation captures the alignment of the TST model with relevant
examples, the ones that are the most similar to a target code snippet,
observed by the distinct relation between the trained TST models ($\bullet$)
and the theoretical maximum. This relation does not hold when considering
randomly sampled negative examples ($\star$). Embeddings rank poorly for
relevant examples, but very good for random examples. These observations
highlight the need to select relevant examples for standalone ranking: some
nuances of similarities in natural language should be _unlearned_.

Figure 3 shows end-to-end and ranking results for different configurations of
TSTR on the $\bullet$ benchmark. A model with too few parameters does not
learn enough, and too large models (likely) overfit. More interesting is the
relation between ranking performance and execution match, where we can use the
former as a proxy to determine the number of parameters of TSTR.

Figure 2: Relation between execution match (top-1) and our pairwise ranking
evaluation with random ($\star$) and relevant ($\bullet$) negative examples on
the M dataset. Ranking with relevant examples shows a relation with code
generation performance. Figure 3: Relation between execution match (top-1) and
our pairwise ranking ($\bullet$) for different fully connected layer
configurations of TSTR on the M dataset. There is a clear relation between
both metrics.

###  5.3 Variation in Language

We show how TSTR handles variations in language by creating three different
testing datasets, with $u_{r}$ and $(u_{p},u_{n})$ coming from train–train,
test–train and test–test.

Results on $\bullet$ are shown in Table 2. We see that TSTR is significantly
less sensitive to language that it has not seen during training (test–train).
TST performs best when the samples are from the same distribution as the
training corpus (train–train). This shows that the model overfits on the
training distribution, as performance does not carry over to other language
distributions.

Table 2: Evaluating influence of variations in language. TSTf uses a FCL on top of frozen sentence embeddings. | test–train | train–train | test–test
---|---|---|---
TSTR | 0.68 | 0.72 | 0.58
TST | 0.57 | 0.90 | 0.57
TSTf | 0.49 | 0.66 | 0.51

###  5.4 Relevant Examples

We show how selecting examples closer to the relevant decision boundary
improves training of TSTR. As baselines, we select (1) random training pairs,
(2) ten times as many random training pairs, and (3) the best $k$ positive
examples (highest code similarity) and negative examples at random.

Table 3 highlights the benefit of selecting the right training set
configuration. Even with many more training pairs, random sampling performs
poorly. Selecting positive samples based on code similarity improves
performance—the system sees more desired examples during training. Selecting
relevant negative examples, which are close to the relevant decision boundary,
shows the model what to forget and improves training of TST.

Table 3: Influence of sampling $u_{p}$ and $u_{n}$ for training. sampling | M | SMCF | Bash
---|---|---|---
random | 0.46 | 0.23 | 0.15
random $\times$ 10 | 0.49 | 0.22 | 0.17
positive only | 0.61 | 0.35 | 0.20
TSTR | 0.68 | 0.67 | 0.42

##  6 Conclusion

We introduce TSTR as a practical improvement of TST for selecting relevant
examples in code generation from natural language. TSTR replaces a fine-tuned
SentenceBERT model with a small, trainable transformation on top of a frozen
embedding model, and provides a strategy for selecting better training
examples. Additionally, we show that TST can be evaluated on pairs of
utterances from the training set that are ranked with respect to a reference
utterance from the testing set, which does not require end-to-end code
generation.

Our experiments show that TSTR outperforms classical TST when the language
distribution of the example bank does not match that of the tests, that
selecting examples closer to the relevant decision boundary improves
performance, and that a pairwise ranking evaluation correlates to end-to-end
code generation performance.

##  7 Limitations

TST assumes that similar code makes for good examples, and this assumption
directly transfers to TSTR. When the code is similar overall, but specific
details are omitted, this can still result in suboptimal examples.

An additional call to an embedding model or endpoint is required to select
relevant examples. Whereas embedding calls are generally cheap333OpenAI
reports a price of $0.0001/1K tokens for its most powerful text-embedding-
ada-002 model (June 2023)., the network overhead can cause lower latency than
inference with a small transformer.

## References

  * Andreas et al. (2020) Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, Ilya Lintsbakh, Andy McGovern, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, Andrei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020.  Task-oriented dialogue as dataflow synthesis.  _Transactions of the Association for Computational Linguistics_ , 8:556–571.
  * Athiwaratkun et al. (2023) Ben Athiwaratkun, Sanjay Krishna Gouda, Zijian Wang, Xiaopeng Li, Yuchen Tian, Ming Tan, Wasi Uddin Ahmad, Shiqi Wang, Qing Sun, Mingyue Shang, Sujan Kumar Gonugondla, Hantian Ding, Varun Kumar, Nathan Fulton, Arash Farahani, Siddhartha Jain, Robert Giaquinto, Haifeng Qian, Murali Krishna Ramanathan, Ramesh Nallapati, Baishakhi Ray, Parminder Bhatia, Sudipta Sengupta, Dan Roth, and Bing Xiang. 2023.  Multi-lingual evaluation of code generation models.  In _International Conference on Learning Representations_.
  * 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, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, and Ming Zhou. 2020.  CodeBERT: A pre-trained model for programming and natural languages.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1536–1547, Online. Association for Computational Linguistics.
  * Khatry et al. (2023) Anirudh Khatry, Joyce Cahoon, Jordan Henkel, Shaleen Deep, Venkatesh Emani, Avrilia Floratou, Sumit Gulwani, Vu Le, Mohammad Raza, Sherry Shi, et al. 2023\.  From words to code: Harnessing data for program synthesis from natural language.  _arXiv preprint arXiv:2305.01598_.
  * Le et al. (2022) Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Chu Hong Hoi. 2022.  Coderl: Mastering code generation through pretrained models and deep reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:21314–21328.
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022.  Competition-level code generation with alphacode.  _Science_ , 378(6624):1092–1097.
  * Lin et al. (2018) Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D. Ernst. 2018.  Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation LREC 2018, Miyazaki (Japan), 7-12 May, 2018._
  * Liu et al. (2021) Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. 2021.  What makes good in-context examples for gpt-3?  _arXiv preprint arXiv:2101.06804_.
  * Liu et al. (2023) Michael Xieyang Liu, Advait Sarkar, Carina Negreanu, Benjamin Zorn, Jack Williams, Neil Toronto, and Andrew D Gordon. 2023.  “what it wants me to say”: Bridging the abstraction gap between end-user programmers and code-generating large language models.  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , pages 1–31.
  * Poesia et al. (2022) Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022.  Synchromesh: Reliable code generation from pre-trained language models.  _arXiv preprint arXiv:2201.11227_.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  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 3982–3992.
  * Singh et al. (2022) Mukul Singh, José Cambronero, Sumit Gulwani, Vu Le, Carina Negreanu, Mohammad Raza, and Gust Verbruggen. 2022.  Cornet: A neurosymbolic approach to learning conditional table formatting rules by example.  _arXiv preprint arXiv:2208.06032_.
  * Wang et al. (2021) Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi. 2021.  Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 8696–8708.


# Status Report of the Gerda Phase II Startup

Valerio D’Andrea, on behalf of the Gerda collaboration V. D’Andrea is with the
Gran Sasso Science Institute (INFN), L’Aquila, Italy (email:
valerio.dandrea@gssi.infn.it).

###### Abstract

The GERmanium Detector Array (Gerda) experiment, located at the Laboratori
Nazionali del Gran Sasso (LNGS) of INFN, searches for $0\nu\beta\beta$ of
76Ge. Germanium diodes enriched to $\sim 86~{}\%$ in the double beta emitter
76Ge(enrGe) are exposed being both source and detectors of $0\nu\beta\beta$
decay. Neutrinoless double beta decay is considered a powerful probe to
address still open issues in the neutrino sector of the (beyond) Standard
Model of particle Physics.

Since 2013, just after the completion of the first part of its experimental
program (Phase I), the Gerda setup has been upgraded to perform its next step
in the $0\nu\beta\beta$ searches (Phase II). Phase II aims to reach a
sensitivity to the $0\nu\beta\beta$ decay half-life larger than $10^{26}~{}$yr
in about 3 years of physics data taking. This exposing a detector mass of
about $35~{}$kg of enrGe and with a background index of about
$10^{-3}~{}$cts/(keV$\cdot$kg$\cdot$yr).

One of the main new implementations is the liquid argon scintillation light
read-out, to veto those events that only partially deposit their energy both
in Ge and in the surrounding LAr.

In this paper the Gerda Phase II expected goals, the upgrade work and few
selected features from the 2015 commissioning and 2016 calibration runs will
be presented. The main Phase I achievements will be also reviewed.

###### Index Terms:

Gerda, double beta decay, germanium, LNGS.

##  I Introduction

The GERmanium Detector Array (Gerda) [1] is an experiment searching for the
neutrinoless double beta ($0\nu\beta\beta$) decay of 76Ge. High-purity
germanium (HPGe) detectors enriched in 76Ge to $\sim 86\%$ are exposed acting
both as sources and detection media.

The experimental signature of $0\nu\beta\beta$ decay is a peak in the spectrum
of the summed energies of the two electrons, released in the nuclear process.
The peak is expected at the $Q_{\beta\beta}$ value that for 76Ge is
$2039~{}$keV.

The events from $0\nu\beta\beta$ decays can be distinguished from
$\gamma$-induced background; infact it is expected that the energy deposition
of the two emitted electrons is localized within few mm (single-site events,
SSE) while $\gamma$-rays deposit energy in several positions (multi-site
events, MSE).

The signals are different for SSE and MSE; surface events from $\alpha$ or
$\beta$ decays also exhibit characteristic shapes. Thus, pulse shape
discrimination (PSD) techniques can improve the experimental sensitivity.

The half-life on $0\nu\beta\beta$ decay can be calculated as [2]:

$T^{0\nu}_{1/2}=\frac{\ln 2\cdot N_{A}}{m_{enr}\cdot N^{0\nu}}\cdot M\cdot
t\cdot\varepsilon$ (1)

where $N_{A}$ is the Avogadro number, $m_{enr}$ is the isotopic mass of the
considered isotope, $N^{0\nu}$ is the observed signal strength, $M$ the total
source mass and $t$ the live time of the measurement. The total efficiency
$\varepsilon$ is the product of several factors:

$\varepsilon=f_{76}\cdot f_{av}\cdot\varepsilon_{FEP}\cdot\varepsilon_{PSD}$
(2)

$f_{76}$ is the fraction of 76Ge atoms, $f_{av}$ is the active volme fraction,
$\varepsilon_{PSD}$ is the signal acceptance by the PSD and
$\varepsilon_{FEP}\sim 90\%$ is the probability that a $0\nu\beta\beta$ decay
releases its entire energy in the detector, losses are due to bremsstrahlung
photons, fluorescence X-rays or electrons escaping the detector active volume.

##  II The Gerda Experiment

Figure 1: Section of the Gerda experiment

The construction of Gerda was tailored to background minimization. The
germanium detectors are mounted in low mass ultra-pure holders and are
directly inserted in $64~{}$m3 of liquid argon (LAr), acting as cooling medium
and shield against external background radiation (Fig. 1 shows the section of
the Gerda setup). The argon cryostat is complemented by a water tank with
$10~{}$m diameter which further shields from neutron and $\gamma$ backgrounds.
It is instrumented with photomultipliers to veto the cosmic muons by detecting
Čerenkov radiation. The muon veto hermeticity is provided by plastic
scintillators installed on the top of the structure. A detailed description of
the experimental setup is in Ref. [1].

A first physics data collection, denoted as Phase I, was carried out from
November 2011 to June 2013. In this phase eight p-type semi-coaxial detectors
enriched in 76Ge from the Heidelberg-Moscow (HdM) [3] and IGEX [4] experiments
and five Broad Energy Germanium (BEGe) detectors were used [5]. Three coaxial
detectors with natural isotopic abundance from the Genius Test Facility (GTF)
project [6, 7] were also installed.

In 2013, at the completion of Phase I, the setup upgrade was started; in 2015
many test and commissioning runs were performed and since January 2016 the
Phase II physics data taking is ongoing.

###  II-A Phase I Results

From November 2011 to May 2013 a global exposure of $21.6~{}$kg$\cdot$yr has
been collected. Data blinding was implemented for the first time in a
$0\nu\beta\beta$ experiment data analysis protocol. Events with energies
within $Q_{\beta\beta}\pm 20~{}$keV were not processed. After the fine energy
calibration, the PSD criteria and the background model were finalized the
window was opened except for $\pm 5~{}$keV ($\pm 4~{}$keV) around
$Q_{\beta\beta}$ for the semi-coaxial (BEGe) detectors; only at the end the
$Q_{\beta\beta}$ region were analyzed.

The Gerda background model [8] predicts a flat energy distribution between
1930 and 2190 keV from Compton events of $\gamma$ rays of 208Tl and 214Bi
decays, degraded $\alpha$ events and $\beta$ rays from 42K and 214Bi.

In the range $Q_{\beta\beta}\pm 5~{}$keV seven events are observed before the
PSD, to be compared to $5.1\pm 0.5$ expected background counts. Three out of
the six events from the semi-coaxial detectors are classified as SSE by the
artificial neural network (ANN) method, consistent with the expectation. The
event in the BEGe data set is rejected by the $A/E$ cut (the powerful PSD
method for the BEGes that uses the ratio between the ampitude of the current
pulse $A$ and the total energy $E$), hence no events remain within
$Q_{\beta\beta}\pm\sigma_{E}$ after PSD.

The combined energy spectrum around $Q_{\beta\beta}$, with and without the PSD
selection, is displayed in Fig. 2.

Figure 2: Combined energy spectrum from all enrGe detectors without (with) PSD
is shown by open (filled) histogram [9]

To derive the signal strength $N_{0\nu}$ and a frequentist coverage interval,
a profile likelihood fit was performed [9]. The fitted function consists of a
constant term for the background and a Gaussian peak for the signal with mean
at $Q_{\beta\beta}$ and standard deviation $\sigma_{E}$ according to the
expected resolution.

The best fit value is $N_{0\nu}=0$ that means no signal events above the
background. The derived half-life limit on $0\nu\beta\beta$ decay is:

$T_{1/2}^{0\nu}>2.1\cdot 10^{25}\text{yr}~{}\text{(90\% C.L.)}$ (3)

including the systematic uncertainty.

Gerda Phase I data show no indication of a peak at $Q_{\beta\beta}$ and the
claim for the observation of $0\nu\beta\beta$ [10] decay in 76Ge is not
supported.

This result is consistent with the limits by HdM and IGEX experiments and
extending the profile likelihood fit including the data sets of those
experiment the best fit yields is still $N_{0\nu}=0$ and a new limit for the
$0\nu\beta\beta$ decay is established:

$T_{1/2}^{0\nu}>3.0\cdot 10^{25}\text{yr}~{}\text{(90\% C.L.)}$ (4)

In addition to the new limit on the $0\nu\beta\beta$, the Phase I data allowed
to establish the new value for the two neutrino accompanied $\beta\beta$ decay
($T_{1/2}^{2\nu}=1.926\pm 0.094\cdot 10^{21}~{}$yr), to search for
neutrinoless $\beta\beta$ decay processes accompanied with Majoron emission
(no signals were found and lower limits of the order of $10^{23}~{}$yr were
set) [11] and to study the two neutrino $\beta\beta$ decay of 76Ge to excited
states of 76Se [12] (no signal observed and new bounds determined for three
transition, two orders of magnitude larger than those reported previously).

##  III Upgrade to Phase II

The Gerda Phase II goal is the reduction of a factor of ten the background
obtained in Phase I and this can only be achieved with an optimized
experimental design. After several years of R & D, a version of the broad
energy germanium (BEGe) detector [13] from Canberra with a thick entrance
window has been selected. The advantages of using the BEGe detectors are their
superior rejection of background with a simple and powerful analysis and their
optimal energy resolution due to a very low detector capacitance.

In addition an active suppression of background by detecting the LAr
scintillation light is introduced.

Figure 3: Phase II assembly of detector array and LAr veto system as it will
be immersed into the cryostat

Fig. 3 shows the core of the Phase II Gerda setup: the Ge detector array,
whose mass is doubled compared to Phase I, is at the center of a vetoed LAr
volume.

The design allows to assemble both the detector array and the surrounding LAr
veto system in the open lock under dry nitrogen atmosphere and to lower both
systems together into the cryostat.

###  III-A BEGe Detectors

Figure 4: Schematic drawing of a BEGe detector

The BEGe detectors for Phase II (5 of them already used in Phase I) are a
modified model BE5030 available from Canberra Semiconductor (Olen). A
schematic view of a BEGe diode is shown in Fig. 4.

The detector is made of p-type HPGe with the Li- drifted n+ contact
($0.7~{}$mm specified thickness) covering the whole outer surface, including
most of the bottom part. The small p+ contact is located in the middle of the
bottom side.

The raw material for the BEGe diodes enriched in 76Gehas been produced in form
of $53.3~{}$kg of enrGeO2 from ECP (Zelonogorsk, Russia) with the 76Geisotope
enriched to $\sim 88~{}\%$. The reduction and purification of the GeO2 was
achieved with an efficiency of $94\%$ yielding $35.5~{}$kg enrGe(6N) for
crystal production at Canberra (Oak Ridge), a total of 9 crystals could be
pulled. The crystals were cut into 30 slices and sent to Canberra (Olen) where
they were transformed into working BEGe detectors with a total mass of
$20.0~{}$kg.

All detectors have been characterized in the HADES underground facility close
to Olen; the relevant operational parameters including active volumes, dead
layers and pulse shape performances have been defined. 29 out of 30 detectors
work according to specifications reaching full depletion with bias voltages
below $5~{}$kV and an energy resolution at $1.3~{}$MeV of $<1.9~{}$keV of FWHM
when operated in a standard vacuum cryostat and standard Canberra Ge detector
front end electronics [5]. In a final step, Al pads for wire bonding were
evaporated on the p+ and n+ substrates of each crystal.

During all production steps, the exposure of the enriched material to the
cosmic radiation has been reduced significantly by shielded transport and
underground storage of the material.

The two main adavantages of using these detectors are the optimal energy
resolution due to the very low input capacitance ($\sim~{}$pF) and the
powerful pulse shape discrimination. The particular position of the p+ and n+
contacts produces a non-uniform electrical field inside the BEGe detectors,
allowing to discriminate the single-site (like the $0\nu\beta\beta$) from the
multi-site events using the $A/E$ ratio: the SSE events have a fixed $A/E$ and
can be discriminate from the typical background events normally MSE.

###  III-B Detector Assembly and Read-Out Electronics

To provide a further background reduction a new holder for detectors, new
contacts and new read-out electronics were implemented for Phase II.

Since the model of the Gerda Phase I background [8] showed that a large
fraction of the background is originated from sources close to the Ge
detectors, in Phase II most of the material close to the Ge detector array
were replaced by material of higher radio-purity and reduced mass. The Phase I
spring-loaded detector contacts have been replaced by wire bonded ones.
Moreover the new holder is made by a plate of $40~{}$g of mono-crystalline
silicon which is intrinsically radio-pure. The silicon plate provides also the
fixation of both the signal and the HV contacts.

The test and commissioning runs showed that, for different reasons, many
detectors had reverse current. Many detectors were sent to Canberra for groove
passivation and the back-to-back detector mounting assemblies were modified to
have the groove looking downward. This to prevent particles floating in the
LAr depositing and stay in the groove triggering the reverse current. As a
consequence of the taken actions the fraction of detectors showing reverse
current significanty decreased.

To take full advantage of the low input capacitance of the BEGe diodes and to
accomplish the more stringent requirements in terms of radio-purity of the
Phase II also the front-end electronics was improved. A new version of the
charge sensitive preamplifiers, called CC3, was developed for Gerda Phase II
[14].

The new preamplifier CC3 is composed of two separate sections: the Very-Front-
End (VFE) section (Fig. 5), consisting of the preamplifier input JFET, the
feedback components (resistor and capacitor) and the main section of the
preamplifier, consisting of operational amplifiers, passive components and
connectors.

Figure 5: Very Front End section of CC3 preamplifier designed for Gerda Phase
II

The VFE section is mounted very close to the detector to improve its
performances. For this reason it must be extremely radio-pure: the input JFET
is a commercial bare die (SF291) connected with bonding wire, the discrete
feedback resistors (of $500~{}$M$\Omega$) is a 0402 SMD ceramic package and
the feedback capacitor ($0.3~{}$pF) is a printed trace. The flexible VFE
circuit has a coplanar waveguide tail to transmit the three relevant signal
(test, feedback and JFET drain) from/to the CC3.

The high mortality of the bare die JFETs during the detector handling
operations motivated to keep the Phase I readout scheme, with the BF862 JFET
close to the second amplifying stage located at $40~{}$cm ($80~{}$cm) above
the top (bottom) detector in the string. The detector-CSA contacts, the CSA
boards and the full coaxial cabling (for Ge, PMTs, SiPMs) have been redesigned
and made out of new material with respect to Phase I; as result their 232Th,
238U, 226Ra contents is reduced by a factor of 3 for the front-end devices and
factor 10 for unit length of the coaxial cables.

The performances obtained by the coupling of the CC3 preamplifier and BEGe
detectors is a FWHM of $\sim 2.6~{}$keV at 2.6 MeV, whit a $20~{}$MHz
bandwidth allowing PSD by the A/E method, $50~{}$mW/channel power dissipation
that is suitable for operation in LAr and a radio-purity of $50~{}\mu$Bq/PCB
for 228Th including connectors.

###  III-C LAr Instrumentation

Fig. 3 shows the LAr veto system: 9 top and 7 bottom PMTs [15] collect light
from a LAr volume of $220~{}$cm height and 49 diameter surrounding the Ge
detector array. A curtain of wavelength shifting fibers, coupled to silicon
photomultipliers (SiPMs) [16], encloses the middle $100~{}$cm length of this
volume and can collect light also outside the diameter of the enclosed
cylinder. Hence the diameter of the vetoed LAr volume at the Ge detector array
level is enlarged.

The upper and lower parts of the vetoed volume, $60~{}$cm in height each,
consist of thin-walled ($0.1~{}$mm) copper cylinders lined by wavelength
shifting reflector foils (Tetratex + TPB), while the fiber curtain is made of
$1\times 1~{}$mm wavelength shifting fibers coated with TPB and coupled in
groups of nine to $3\times 3$ SiPM arrays.

Pointing with their diagonals to the central axis, the total of 810 fibers
covers almost $80\%$ of the circumference.

##  IV Start of Phase II Data Taking

The commissioning phase started in July 2015 and several runs were performed
with different detector configurations.

On December 20th, 2015 the Phase II configuration with all the detectors
mounted in the array was achieved and the data taking has been started.

Figure 6: Full detector array of Gerda Phase II mounted on December 2015
Figure 7: Schematic view of the strings: the BEGe detectors are arranged in 4
strings (in string 6 there is also a coaxial), the coaxial in the other 3
strings

Fig. 6 shows a picture of the full array just before the immersion in LAr:
seven enrGe plus three natural coaxials (both from Phase I) and thirty new
enrGe BEGe detectors for a total of 40 detectors accounting for $35.6~{}$kg of
enrGe and $7.6~{}$kg of natGe are organized in seven strings; Fig. 7 shows a
schematic view of the the detector arrangement. The BEGes ($20~{}$kg of enrGe)
are organized in three strings of eight and one string of six detectors, the
coaxials ($15.6~{}$kg of enrGe) are organized in three strings of three
detectors, plus one coaxial in a BEGe string. Each detector string is
surronded by a nylon mini-shroud, preventing the 42K ions from being drifted
and diffused at the detector surfaces.

After the immersion of the array all 40 detectors are working, most of them
are at operational voltage showing a leakage current $<100~{}$pA, 3 BEGes and
one coaxial are showing a value of LC$~{}\gtrsim 100~{}$pA and needed a
decrease of the bias voltage.

The energy scale of detectors is determined by weekly irradiating the Ge
detector array by three 228Th ($20$-$30~{}$kBq) sources. The stability of the
setup is monitored comparing the reconstructed peak positions in different
calibrations.

Fig. 8 shows the energy shift for the $2614.5~{}$keV peak between the
calibration runs of January 29th, February 3rd, February 9th and February
11th.

Figure 8: Energy shift of the $2614.5~{}$keV peak in the comparison between
the calibration runs of January 29th and February 3rd (in blue), February 3rd
and February 9th (in red) and February 9rd and February 11th (in green). The
horizontal axis follows the detector progressive number and the top legend
reports the string number

The horizontal axis reports the detector progressive number following its
arrangement in the strings starting from string 1 to string 7. Excluding few
cases, the shifts are in the range between $-1~{}$keV and $+1~{}$keV.

The performances of the setup are also established using the calibration data.
The energy spectrum is reconstructed and the resolution (in terms of FWHM) of
the peaks is calculated. In Gerda a novel filtering method was developed in
order to improve the energy resolution [17].

From noise theory [18], it can be shown that the infinite cusp is the optimal
filter to abate both series and parallel noise. In a real case where a limited
waveform length is recorded ($160~{}\mu$s in Gerda) and in presence of low
frequency disturbances, a Zero Area, modified Cusp (ZAC), finite impulse
response filter has shown to improve the energy resolution of about
$0.3~{}$keV both for coaxials and BEGes, whit respect to gaussian filter. An
example of such filter is in Fig. 9, the central flat-top (of $\sim 1~{}\mu$s)
allows for full charge collection.

Figure 9: Zero-Area finite-length Cusp (ZAC) filter (in red), composed of the
finite-length cusp (in green) from which two parabolas are subtracted on the
cusp sides (in blue)

Applying this optimized method to the Phase I calibration data, the average
energy resolutions at the 208Tl $2614.5~{}$keV line were of
$(2.76^{+0.08}_{-0.06})~{}$keV and $(4.32^{+0.38}_{-0.30})~{}$keV for BEGes
and coaxials respectively [17]. The averages are evaluated among different
detectors on tenths of independent calibrations. The errors represents the
FWHM half-spread among 4 (6) BEGes (COAX) detectors.

The FWHMs of the $2614.5~{}$keV peak in three calibration runs of Phase II are
showed in Fig. 10; both for BEGes and coaxials, in the figure the horizontal
axis follows the detector progressive number and the top legend reports the
string number. Strings 1, 3 and 4 contain only BEGes, string 2, 5 and 7 only
coaxials, string 6 contains six BEGes and one coaxial. All the values reported
are calculated using the optimal ZAC filter for each detector.

Figure 10: FWHM at $2614.5~{}$keV for three calibration runs during the
beginning of Phase II, are included all BEGe and coaxial detectors. Figure 11:
FWHM of the $A/E$ ratio for DEP events in BEGe detectors at the beginning of
Phase II data taking Figure 12: Background spectrum of beginning of Phase II

The Phase II energy resolutions, evaluated for the three considered
calibrations, is in the range from $2.4~{}$keV to about $5.9~{}$keV for the
BEGes and from $3.2~{}$keV to $4.9~{}$keV for the coaxials. If the detectors
with known problems (number 6, 25 and 27) are not included, the FWHM ranges
are $2.4~{}$keV - $4.0~{}$keV and $3.2~{}$keV - $4.1~{}$keV for the BEGes and
the coaxials respectively.

Fig. 10 reveals that the BEGes energy resolution correlates to the detector
position in the string, that in turn scales with the length of the detector to
JFET contact. This trend is found for all the four BEGe strings and is still
not completely understood, is not fully unexpected: the longer the contact,
the larger its stray capacitance. This is confirmed by the analysis of the FFT
noise spectra, not shown here: the white noise scales with the detector-to-
JFET distance. Detailed analysis is in progress to model and finally improve
the noise. For the coaxials the same trend is not found: apart from individual
detector peculiarities, this may be related to the different ratios of
parasitic vs intrinsic detector capacity for the BEGe than for the coaxial
detectors. The first have an intrinsic capacity of a couple of pF, while the
latter have tens of pF: hence the stray capacitance of long contacts and the
parasitic of the exposed BEGe p+ contacts, accounts for a larger fraction of
their intrinsic capacity. This hypothesis has to be verified.

Another important parameter to evaluate the performances of the BEGe detectors
is the resolution of the $A/E$ ratio; this is evaluated on the double escape
peak (DEP) of the 208Tl $2614.5~{}$keV line. This line shows up at
$1592.5~{}$keV in the calibration spectra; because of the specificity of the
$\gamma$-pair production interaction followed by the double escape of the two
$511~{}$keV $\gamma$s generated in the e+ annihilation, this line is mostly
populated by SSE events. The resolution of the $A/E$ parameter distribution of
DEP events is an indicator of the capability of resolving SSE from MSE, hence
to discriminate the background.

Fig. 11 shows the percentage FWHM of $A/E$ for BEGe detectors combining the
first 228Th Phase II calibration runs. It shows the same trend of Fig. 10: the
FWHM of the $A/E$ ratio also scales with the position of the detector in the
string and better values (around $1.5~{}\%$) are obtained for the top
detectors.

A first Phase II background spectrum cut at $1.7~{}$MeV, normalized to the
present exposure of $2.6~{}$kg$\cdot$yr, is shown in Fig. 12.

The spectrum shows the expected prominent structures: the low energy region
(up to $500~{}$keV) is dominated by the long-lived 39Ar isotope; from $600$ to
$1400~{}$keV the $2\nu\beta\beta$ spectrum shows up; then the $1462~{}$keV and
$1525~{}$keV $\gamma$-lines from 40K and 42K respectively are visible.

##  V Conclusion

After Gerda Phase I established a new important limit on $0\nu\beta\beta$
decay of 76Ge, the Phase II started in January 2016.

All detectors are working and the performances of the first period of data
taking indicate that the noise could be improved mitigating the parasitic
sources; this will improve both energy resolution and PSD performances.

The Gerda Phase II physics program is to take data for about three years in
order to obtain $100~{}$kg$\cdot$yr of exposure and searching for the 76Ge
$0\nu\beta\beta$ or improving both the half-life and the effective Majorana
neutrino mass limits, possibly attaining the top border of the neutrino masses
inverted hierarchy region.

## Acknowledgment

The Gerda experiment is supported financially by the German Federal Ministry
for Education and Research (BMBF), the German Research Foundation (DFG) via
the Excellence Cluster Universe, the Italian Istituto Nazionale di Fisica
Nucleare (INFN), the Max Planck Society (MPG), the Polish National Science
Center (NCN), the Foundation for Polish Science (MPD programme), the Russian
Foundation for Basic Research (RFBR), and the Swiss National Science
Foundation (SNF). The institutions acknowledge also internal financial
support. The Gerda collaboration thanks the directors and the staff of the
LNGS for their continuous strong support of the Gerda experiment.

## References

  * [1] K. H. Ackermann et al., Gerda Collaboration, Eur. Phys. J. C 73, 2330 (2013) arXiv:1212.4067.
  * [2] F.T. Avignone III, G.S. King III, Y.G. Zdesenko, New J. Phys. 7, 6 (2005).
  * [3] M. Gunther et al., Phys. Rev. D 55, 54 (1997).
  * [4] C.E. Aalseth et al., Nucl. Phys. Proc. Suppl. 48, 223 (1996).
  * [5] M. Agostini et al., Gerda Collaboration, Eur. Phys. J. C 75, 39 (2015) arXiv:1410.0853
  * [6] L. Baudis et al., Phys. Rep. 307, 301 (1998).
  * [7] H.V. Klapdor-Klingrothaus et al., Nucl. Instrum. Methods A 481, 149 (2002).
  * [8] M. Agostini et al., Gerda Collaboration, Eur. Phys. J. C 74 2764 (2014) arXiv:1306.5084.
  * [9] M. Agostini et al., Gerda Collaboration, Phys. Rev. Lett. 111, 122503 (2013) arXiv:1307.4720.
  * [10] H. V. Klapdor-Kleingrothaus et al., Phys. Lett. B 586, 198 (2004) arXiv:hep-ph/0404088.
  * [11] M. Agostini et al., Gerda Collaboration, Eur. Phys. J. C 75, 416 (2015) arXiv:1501.02345.
  * [12] M. Agostini et al., Gerda Collaboration, J. Phys. G: Nucl. Part. Phys. 42 (2015) 115201 arXiv:1506.03120.
  * [13] D. Budjáš et al., J. Instrum. 4, P10007 (2009).
  * [14] S. Riboldi et al., (NSS/MIC), (2012) IEEE, p. 782-785.
  * [15] M. Agostini et al., Gerda Collaboration, J. Phys.: Conf. Ser. 375, 042009 (2012).
  * [16] J. Janicskó Csáthy et al., Nucl. Instr. Methods 654, 225-232 (2011).
  * [17] M. Agostini et al., Gerda Collaboration, Eur. Phys. J. C 75, 255 (2015) arXiv:1502.04392.
  * [18] E. Gatti, P. F. Manfredi, Riv. Nuovo Cim. 9, 1 (1986).


# Combining Neural Network Models for Blood Cell Classification

1st Indraneel Ghosh  Department of Computer Science and Information Systems
Department of Biological Sciences
Birla Institute of Technology and Science
Pilani, Rajasthan, India
<EMAIL_ADDRESS>2nd Siddhant Kundu  Department of Computer
Science and Information Systems
Birla Institute of Technology and Science
Pilani, Rajasthan, India
<EMAIL_ADDRESS>
###### Abstract

The objective of the study is to evaluate the efficiency of a multi layer
neural network models built by combining Recurrent Neural Network(RNN) and
Convolutional Neural Network(CNN) for solving the problem of classifying of
different kind of White Blood Cells. This can have applications in the
pharmaceutical and healthcare industry for automating the analysis of blood
tests and other processes requiring identifying the nature of blood cells in a
given image sample. It can also be used in diagnosis of various blood related
diseases in patients.

###### Index Terms:

CNN, LSTM, RNN, Cuda, WBC Classification

##  I Introduction

White Blood Cells are an important component of our immune system. The
concentration of various WBCs play an important role in determining the health
of our body. Automating the process of detection of these blood cells
accurately can help expedite various medical processes. Each class of White
Blood Cell is unique. They have differences in texture, color size and
morphology. Our approach attempts to classify the WBCs based on the latent
features of their images.

##  II Methods

The two main segments of the architecture of our proposed neural network are a
Convolutional Neural Network and a Recurrent Neural Network, both trained
using the same image data.

###  II-A Convolutional Neural Networks

A Convolutional Neural Network (CNN) is a type of neural network containing
cells that extract features from an input by moving over it with a small
window, called a kernel. The kernel moves over the entire input, and the
portion of the image captured in the kernel window is checked for features
corresponding to the one the cell has learned to detect. Applied sequentially,
Convolutional Neural Networks are capable of extracting both high-level and
low-level features. They are typically applied to images, where the usage of a
simple feedforward network would make the hidden layers unnecessarily large
and computationally expensive, and also prone to overfitting.

###  II-B Recurrent Neural Networks

A Recurrent Neural Network (RNN) is a variation of standard feedforward
networks where the output of a layer is dependent not only on the current
input, but also the set of inputs that has come before. This is useful for
sequence detection and generation. They provide a significant advantage when
the inputs obtained before can be used to predict what kind of output comes
later.

###  II-C The Advantages of LSTMs

The standard RNN architecture uses a hidden state $h_{t}$ in addition to an
input and an output. Its equations can be represented as:

$h_{t}=\tanh(W_{hh}h_{t-1}+W_{xh}X_{t})$ (1) $y_{t}=\sigma(W_{hy}h_{t})$ (2)

One of the biggest challenges in the model that we have built is handling
long-term dependencies. Theoretically, an RNN is capable of handling long term
dependencies with careful parameter selection. However, it has been noted that
in practice this is not true[5].
Long Short Term Memory Networks (LSTMs) were created to handle these long term
dependencies specifically[6]. As a result, we used LSTM while building our
model. Their structure may be described as:

$f_{t}=\sigma(W_{f}[h_{t-1},X_{t}]+b_{f})$ (3)
$i_{t}=\sigma(W_{i}[h_{t-1},X_{t}]+b_{i})$ (4)
$\hat{C_{t}}=\tanh(W_{C}[h_{t-1},X_{t}]+b_{C})$ (5)
$C_{t}=f_{t}*C_{t-1}+i_{t}*\hat{C_{t}}$ (6)
$o_{t}=\sigma(W_{o}[h_{t-1},X_{t}]+b_{o})$ (7) $h_{t}=o_{t}*\tanh(C_{t})$ (8)

Here, $X_{t}$ is the input vector at timestamp t, which denotes the tth item
in the time series form of the input. $h_{t}$ denotes the hidden state of the
LSTM, which works in roughly the same manner as for a regular RNN, and is used
for storing information about previous inputs. $f_{t}$ denotes the forget gate
- i.e. the part of the previous hidden state that needs to be forgotten for
the current input. $i_{t}$ denotes the input gate, which decides which parts
of the input vector should be stored in the next hidden state. $C_{t}$ denotes
the cell state at t, which is used for output generation, and $\hat{C_{t}}$
denotes the set of values to be updated at timestamp t. Finally, $o_{t}$
denotes the output of the LSTM.

Our work combines the CNN layer, that classifies images based on a hierarchy
of features ranging from straight lines and curves to specific nuclear shapes,
and the RNN layer, that uses the fact that we are classifying white blood cell
images that will contain certain fixed low level features leading to some more
fixed high level features, in sequence. To obtain a faster, optimized model we
make use of NVIDIA CUDA®
Deep Neural Network library (cuDNN) which significantly reduces the training
time of the model.

###  II-D Dataset

The dataset obtained from Kaggle contains 12,500 augmented images of blood
cells in JPEG format with the accompanying cell type labels. The cell types
are Eosinophil, Lymphocyte, Monocyte, and Neutrophil. There are approximately
3,000 images for each of the four cell types. This dataset is accompanied by
an additional dataset containing the original pre-augmented 410 images as well
as two sub-type labels and also bounding boxes for labeling (JPEG+XML) each of
the cells in these images. It also contains 2500 augmented images as well as
four additional subtype labels (JPEG+ CSV). There are approximately 2,000
augmented images for each of the four class as compared to 88, 33,21 and 207
of the original images.[3]

Figure 1: A Labelled Blood Cell Image

###  II-E Data Pre-Processing

Since the dataset we have is small, we decided to augment the images by
rotation, reflection about the horizontal axis and shifting both horizontally
and vertically. We must ensure that the computation time without losing too
much accuracy. Hence, the size of the input image was reduced to $80\times
60$. Scaling transformations are not applied because the correct
identification of the type of cell depends on the size of the nuclei.

The four cell types have been transformed into a 4 dimensional vector with
one-hot encoding - i.e., all components are zero, except the one corresponding
to the appropriate class. For example, the cell type ’NEUTROPHIL’ may be
encoded as [0,0,1,0], and ’MONOCYTE’ may be encoded as [1,0,0,0]. This
transformation allows us to use the softmax loss function[4], defined as:

$y_{k}=\frac{\exp(\phi_{k})}{\sum^{c}_{j}\exp(\phi_{j})},$ (9)

###  II-F Model

Our Model consists of five parts - the Input Layer, the CNN Layer, the RNN
Layer, the Merge Layer and the Output Layer - as detailed below.

####  II-F1 Input Layer

This is the simplest layer of the network. It takes the image data as an
input, and converts it into a tensor of the appropriate size -
$img\\_rows\times image\\_columns\times 3$ (one for each primary color).

####  II-F2 CNN Layer

This is the segment consisting of convolutional cells that scan the image for
present features. In our model, it contains 4 layers. The first layer is a
convolutional layer that consists of 32 cells, and the second layer is also a
convolutional layer that consists of 64 cells. Each layer uses a $3\times 3$
kernel. It is followed by pooling to reduce the size of the output, a dropout
layer to reduce overfitting and a layer that flattens the output to 2D.

####  II-F3 RNN Layer

This layer consists of LSTMs that learn to detect recurring features in the
images. In our model, the image is converted to grayscale before being passed
to the RNN, to reduce overfitting due to learning color patterns. This is
likely to happen since the dataset is quite small (even after augmentations)
and RNNs do not deal with overfitting due to color in images as well as CNNs
due to their similarities with standard feedforward networks. Our model has 2
LSTM layers. Each LSTM layer uses 64 LSTMs, and is followed by a dropout layer
to reduce overfitting.

####  II-F4 Merge Layer

The merge layer takes the CNN layer’s output and the RNN layer’s output and
returns the element-wise product of the two. Both layers were constructed to
have 64 neurons at the time of merging. Therefore, we get the combination of
the CNN and RNN parts. A 128 cell layer with ReLU activation follows this for
another round of processing, followed by a final dropout layer, feeding into
the output layer.

####  II-F5 Output Layer

The output layer has 128 cells, and applies the softmax function to evaluate
which class the given input image is most likely to fall into, as defined by
the input set, according to equation (9). Since the input set only has single-
class data, we decided to use the softmax function to improve our model’s
classification power.

###  II-G Training

For training the network, we decided to use the predefined split in the
dataset. Both the branches of the network, the CNN and the RNN, are trained
simultaneously. The loss function used is categorical cross-entropy, since we
have a four-category classification problem. The optimizer used is Adadelta,
since it allows for adaptive learning rate based on previous gradients.

For both the four-way and the two-way classification problems, the model is
trained for 70 epochs, with an initial learning rate of 1.0 and a batch size
of 32.

##  III Experiments and Results

For comparative purposes, we tested a CNN-only solution to the problem, under
the same conditions as the hybrid solution. A table comparing the two is shown
below:

TABLE I: Comparison of Accuracies of the Different Architectures Architectures | Classification Accuracy
---|---
| 2 Way Classification | 4 Way Classification
CNN | 93.76% | 86.16%
CNN + RNN | 94.13% | 87.29%

##

Figure 2: CNN only 4 way classification

Figure 3: CNN only 2 way classification

Figure 4: CNN +RNN 4 way classification

Figure 5: CNN+RNN 2 way classification

## Conclusion

We can see that the CNN-RNN hybrid architecture offers better results than the
CNN-only network - for the four-way classification problem, approximately 8%
of the cases misclassified by the CNN-only solution are classified correctly
by the CNN-RNN combination, assuming that the hybrid network does not
misclassify the items that are correctly classified by the CNN-only network.
For the two-way classification problem, approximately 6% of the misclassified
cases are correctly classified by the hybrid network. With the usage of the
optimized cuDNN version of the LSTM layers, the training time is roughly the
same as with the pure CNN network (approximately 13 seconds per epoch for CNN
only, approximately 17 seconds per epoch on CNN+RNN). Thus, we can conclude
that the usage of an RNN alongside a CNN leads to improved performance.

## Acknowledgement

The authors would like to thank the Department of Biological Sciences,BITS
Pilani for providing us with an opportunity to present our work and fine-
tuning our ideas.

## References

  * [1] Liang, Gaobo & Hong, Huichao & Xie, Weifang & Zheng, Lixin. (2018). Combining Convolutional Neural Network with Recursive Neural Network for Blood Cell Image Classification. IEEE Access. PP. 1-1. 10.1109/ACCESS.2018.2846685.
  * [2] http://cs231n.github.io/convolutional-networks/
  * [3] Mooney, T. Kaggle Dataset for Blood Cell Images
  * [4] Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Berlin, Heidelberg
  * [5] Y. Bengio, P. Simard and P. Frasconi, ”Learning long-term dependencies with gradient descent is difficult,” in IEEE Transactions on Neural Networks, vol. 5, no. 2, pp. 157-166, March 1994. doi: 10.1109/72.279181
  * [6] Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Comput. 9, 8 (November 1997), 1735-1780. DOI=http://dx.doi.org/10.1162/neco.1997.9.8.1735


#  Largest subgraph from a hereditary property in a random graph

Noga Alon Department of Mathematics, Princeton University, Princeton, NJ
08544, USA and Schools of Mathematics and Computer Science, Tel Aviv
University, Tel Aviv 6997801, Israel. Email<EMAIL_ADDRESS>Research supported in part by NSF grant DMS-2154082 and by USA-Israel BSF
grant 2018267. Michael Krivelevich  School of Mathematical Sciences, Tel Aviv
University, Tel Aviv 6997801, Israel. Email<EMAIL_ADDRESS>Research supported in part by USA-Israel BSF grant 2018267. Wojciech Samotij
School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801,
Israel. Email<EMAIL_ADDRESS>Research supported in part by the
Israel Science Foundation grant 2110/22.

###### Abstract

We prove that for every non-trivial hereditary family of graphs ${\cal P}$ and
for every fixed $p\in(0,1)$, the maximum possible number of edges in a
subgraph of the random graph $G(n,p)$ which belongs to ${\cal P}$ is, with
high probability,

$\left(1-\frac{1}{k-1}+o(1)\right)p{n\choose 2},$

where $k$ is the minimum chromatic number of a graph that does not belong to
${\cal P}$.

##  1 Introduction

Let ${\cal P}$ be an arbitrary hereditary property of graphs. We assume
throughout that ${\cal P}$ is non-trivial, i.e., it contains all edgeless
graphs and misses some graph. For a graph $G$, let $\operatorname{ex}(G,{\cal
P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to
${\cal P}$; the above definition of non-triviality guarantees that this number
is well-defined. In this note we determine, for every fixed edge probability
$p\in(0,1)$, the typical asymptotic value of $\operatorname{ex}(G,{\cal P})$
for the random graph $G=G(n,p)$ as $n$ tends to infinity. This is stated in
the following theorem.

######  Theorem 1.1.

Let ${\cal P}$ be a non-trivial hereditary property of graphs and let
$k=k({\cal P})\geq 2$ denote the minimum chromatic number of a graph that does
not belong to ${\cal P}$. Then, for every fixed $p\in(0,1)$, the random graph
$G=G(n,p)$ satisfies, with high probability:

$\operatorname{ex}(G,{\cal P})=\left(1-\frac{1}{k-1}+o(1)\right)p{n\choose
2},$

where the $o(1)$-term tends to $0$ as $n$ tends to infinity.

In fact, our argument yields the assertion of the theorem under the weaker
assumption that $n^{-c}\leq p=p(n)$ and $1-p\geq n^{-c}$ for some positive
constant $c$ that depends only on the property ${\cal P}$, see Proposition 2.1
below for the sparse case, the dense case follows in the same way.

In the statement above and throughout the rest of this note, the term “with
high probability” (whp, for short) means, as usual, with probability tending
to $1$ as $n$ tends to infinity.

The assertion of Theorem 1.1 for principal monotone properties (that is,
properties defined by avoiding a single graph) is known in a strong form, and
the precise range of the probability $p=p(n)$ for which it holds has been
determined in [5, 7], following a considerable number of earlier results
establishing special cases. There are, however, far more hereditary properties
than monotone ones. A few arbitrarily chosen examples are perfect graphs,
graphs with no induced hole of length $57$, graphs containing no set of $10$
vertices that span exactly $34$ edges, or intersection graphs of discs in the
plane.

The (short) proof of the theorem is presented in the next section. The third
and final section contains some concluding remarks and open problems.
Throughout the rest of this note, we systematically omit all floor and ceiling
signs.

##  2 The proof

In this section, we prove Theorem 1.1. Let ${\cal P}$ be a hereditary property
and put $k=k({\cal P})~{}(\geq 2)$. Note, first, that every graph $G$ contains
a $(k-1)$-colorable subgraph with at least $(1-\frac{1}{k-1})|E(G)|$ edges.
Since every such subgraph belongs to ${\cal P}$ by the definition of
$k=k({\cal P})$, when $G=G(n,p)$ with $p\gg n^{-2}$, then the assertion that

$\operatorname{ex}(G,{\cal P})\geq\left(1-\frac{1}{k-1}-o(1)\right)p{n\choose
2}$ (1)

holds whp follows from the (standard and easy) fact that $|E(G)|$ is
concentrated around its expectation as long as $pn^{2}$ tends to infinity.

We now turn to the proof of the upper bound on $\operatorname{ex}(G,{\cal
P})$. We start by observing that, for every graph $G$ and all $L\notin{\cal
P}$, we have $\operatorname{ex}(G,{\cal P})\leq\operatorname{ex}(G,{\cal
F}_{L})$, where ${\cal F}_{L}$ is the property of not containing $L$ as an
induced subgraph. The following proposition establishes an optimal upper bound
on $\operatorname{ex}(G,{\cal F}_{L})$ in the case where $G$ is a _sparse_
binomial random graph. Recall that the $2$-density of a nonempty graph $L$ is
defined by

$m_{2}(L)=\max\left\\{\frac{|E(K)|-1}{|V(K)|-2}:K\subseteq L\text{ with
}|E(K)|\geq 2\right\\},$

when $L$ has at least two edges, and $m_{2}(K_{2})=1/2$. This notion is
defined so that $p\gg n^{-1/m_{2}(L)}$ precisely when, for every subgraph
$K\subseteq L$ with at least two edges, the expected number of copies of $K$
in $G(n,p)$ is asymptotically much bigger than $pn^{2}$. In particular, it is
not hard to see that the lower-bound assumption $p\gg n^{-1/m_{2}(L)}$ is
necessary.

######  Proposition 2.1.

Let $L$ be a nonempty graph. If $n^{-1/m_{2}(L)}\ll p=p(n)\ll 1$, then the
random graph $G=G(n,p)$ whp satisfies

$\operatorname{ex}(G,{\cal
F}_{L})\leq\left(1-\frac{1}{\chi(L)-1}+o(1)\right)p\binom{n}{2}.$

We will derive the proposition from the following “supersaturated” version of
the random analogue of Turán’s theorem in $G(n,p)$ proved by Conlon and Gowers
[5] (under an additional technical assumption on $L$) and by Schacht [7] (in
full generality):

######  Theorem 2.2 ([5, 7]).

For every nonempty graph $L$ and every ${\varepsilon}>0$, there exists
$\delta>0$ such that the following holds for every $p=p(n)\gg
n^{-1/m_{2}(L)}$. With high probability, every subgraph $G^{\prime}$ of the
random graph $G(n,p)$ with

$|E(G^{\prime})|\geq\left(1-\frac{1}{\chi(L)-1}+{\varepsilon}\right)p\binom{n}{2}$

contains at least $\delta n^{|V(L)|}p^{|E(L)|}$ copies of $L$.

######  Remark.

Even though the above result is not explicitly stated in either [5] or [7],
one obtains it easily by: (i) using the stronger conclusion of [5, Theorem
9.4] while deriving [5, Theorem 10.9]; (ii) replacing [7, Theorem 3.3] with
its stronger version [7, Lemma 3.4] in the derivation of [7, Theorem 2.7]. A
stronger version of Theorem 2.2, with optimal dependence of $\delta$ on
${\varepsilon}$ and $H$, is stated and proved in [6, Theorem 1.10].

###### Proof of Proposition 2.1.

It suffices to show that, for every fixed ${\varepsilon}>0$, with high
probability, every subgraph $G^{\prime}\subseteq G$ with at least
$(1-\frac{1}{\chi(L)-1}+{\varepsilon})p\binom{n}{2}$ edges contains more (not
necessarily induced) copies of $L$ than the total number of copies of all
strict supergraphs of $L$ (with the same vertex set) in $G$. (We note that a
similar idea was used in [4] to derive upper bounds on induced Ramsey
numbers.) On the one hand, Theorem 2.2 implies that each $G^{\prime}$ as above
contains at least $\delta n^{|V(L)|}p^{|E(L)|}$ copies of $L$. On the other
hand, a simple application of Markov’s inequality gives that, with probability
$1-O(\sqrt{p})$, say, the total number of copies of all strict supergraphs of
$L$ is at most $O(n^{|V(L)|}p^{|E(L)|+1/2})$. Since we assume that $p\ll 1$,
the latter of the above two quantities is much smaller. ∎

The following statement is a straightforward corollary of the definition of
$k$ and Proposition 2.1 invoked with some $L\notin{\cal P}$ with $\chi(L)=k$.

######  Corollary 2.3.

For every ${\varepsilon}>0$, there exists a graph $H$ such that

$\operatorname{ex}(H,{\cal
P})<\left(1-\frac{1}{k-1}+{\varepsilon}\right)e(H).$

We will now deduce the statement of Theorem 1.1 from Corollary 2.3 and the
following standard probabilistic estimate.

######  Lemma 2.4.

Let $H$ be a fixed graph, let ${\varepsilon}>0$ be a small positive real and
let $p\in(0,1)$ be a fixed real. Let $G=G(n,p)$ be the random graph and let
$c=c(H,n,p)$ be the expected number of induced copies of $H$ in $G$ that
contain a fixed edge of $G$. Then, whp, for every edge $e$ of $G$ the number
of induced copies of $H$ in $G$ containing $e$ is at least
$(1-{\varepsilon})\mu$ and at most $(1+{\varepsilon})\mu$.

###### Proof.

Fix an edge $e$ of $K_{n}$, assume it belongs to $E(G)$, and apply the edge
exposure martingale to the random variable $X_{e}$ counting the number of
induced copies of $H$ in $G$ that contain $e$. As $p$ and $H$ are fixed, the
expectation of this random variable is $\mu=\Theta(n^{h-2})$, where $h$ is the
number of vertices of $H$ and the hidden constant in the $\Theta$-notation is
a function of $p$ and $H$. The existence or nonexistence of each of the
potential $2n-4$ edges of $G$ (besides $e$) incident with $e$ can change the
value of $X_{e}$ by at most $O(n^{h-3})$. Similarly, each of the
${{n-2}\choose 2}$ other edges can change the value of $X_{e}$ by at most
$O(n^{h-4})$. Therefore, by Azuma’s Inequality (see, e.g., [2, Chapter 7]),
the probability that $X_{e}$ deviates from its expectation by

$\lambda\cdot[(2n-4)O(n^{2h-6})+{{n-2}\choose
2}O(n^{2h-8})]^{1/2}=\lambda\cdot O(n^{h-5/2})$

is at most $2e^{-\lambda^{2}/2}$. In particular, the probability that $X_{e}$
deviates from its expectation $\mu$ by $a\cdot\mu\frac{\sqrt{\log
n}}{\sqrt{n}}$ is at most $n^{-\Omega(a^{2})}$. Taking a sufficiently large
constant $a$, this implies the desired result by the union bound. ∎

###### Proof of Theorem 1.1.

Let ${\cal P}$ and $k=k({\cal P})$ be as in the statement of the theorem. Fix
a small real ${\varepsilon}>0$ and let $H$ be the graph from Corollary 2.3.
Fix $p\in(0,1)$ and let $G=G(n,p)$ be the binomial random graph. Let ${\cal
H}=\\{H_{i}\\}_{i\in I}$ be the collection of all induced copies of $H$ in
$G$. By Lemma 2.4, whp the number of subgraphs $H_{i}$ containing any edge of
$G$ is at least $(1-{\varepsilon})\mu$ and at most $(1+{\varepsilon})\mu$,
where $\mu>0$ is the expected number of such subgraphs. Assuming this holds,
let $G^{\prime}$ be a subgraph of $G$ that belongs to ${\cal P}$. We need to
estimate the number of edges of $G^{\prime}$ from above. We will do so by
comparing two bounds on the size of the set $S$ of all ordered pairs
$(e,H_{i})$, where $e$ is an edge of $G^{\prime}$, $H_{i}\in{\cal H}$, and $e$
is also an edge of $H_{i}$. Since every edge of $G^{\prime}$ is contained in
at least $(1-{\varepsilon})\mu$ of the graphs $H_{i}$, we have:

$|S|\geq|E(G^{\prime})|(1-{\varepsilon})\mu.$ (2)

On the other hand, since $H$ satisfies the assertion of Lemma 2.3,

$|S|\leq|{\cal H}|\left(1-\frac{1}{k-1}+{\varepsilon}\right)|E(H)|$ (3)

as every $H_{i}$ can contain at most $(1-\frac{1}{k-1}+{\varepsilon})|E(H)|$
edges of $G^{\prime}$. Indeed,

$(V(H_{i}),E(G^{\prime})\cap E(H_{i}))$

is an induced subgraph of $G^{\prime}$, and as $G^{\prime}$ lies in ${\cal P}$
which is hereditary, so does this graph. Therefore, each $H_{i}\in{\cal H}$
can contain at most $(1-\frac{1}{k-1}+{\varepsilon})|E(H)|$ edges of
$G^{\prime}$. Finally, since no edge of $G$ lies in more than
$(1+{\varepsilon})\mu$ members of ${\cal H}$, it follows that

$|{\cal H}||E(H)|\leq|E(G)|(1+{\varepsilon})\mu.$ (4)

Combining (2), (3), and (4), we conclude that

$|E(G^{\prime})|(1-{\varepsilon})\mu\leq|S|\leq|{\cal
H}|\left(1-\frac{1}{k-1}+{\varepsilon}\right)|E(H)|\\\
\leq\frac{|E(G)|(1+{\varepsilon})\mu}{|E(H)|}\left(1-\frac{1}{k-1}+{\varepsilon}\right)|E(H)|=\left(1-\frac{1}{k-1}+{\varepsilon}\right)|E(G)|(1+{\varepsilon})\mu.$

Therefore

$|E(G^{\prime})|\leq\left(1-\frac{1}{k-1}+{\varepsilon}\right)|E(G)|\frac{1+{\varepsilon}}{1-{\varepsilon}}<\left(1-\frac{1}{k-1}+4{\varepsilon}\right)|E(G)|,$

where here we used that ${\varepsilon}>0$ is small. Since ${\varepsilon}$ can
be chosen to be arbitrarily small, this shows that whp

$\operatorname{ex}(G,{\cal
P})\leq\left(1-\frac{1}{k-1}+o(1)\right)|E(G)|=\left(1-\frac{1}{k-1}+o(1)\right)p{n\choose
2}.$

This, together with (1), completes the proof of the theorem. ∎

##  3 Concluding remarks

  * •

Theorem 1.1 can be proved in a more self-contained way, using Szemerédi’s
Regularity Lemma and following the approach in [1, Section 4.4]. Since unlike
the proof described here, this proof does not work for $p\leq
n^{-{\varepsilon}}$ when ${\varepsilon}>0$ is fixed, we omit the details.

  * •

It may be interesting to characterize all edge probabilities $p$ for which the
assertion of Theorem 1.1 holds. It is not difficult to describe hereditary
properties (even monotone ones) for which the fraction of edges of $G(n,p)$
that lie in a maximum subgraph that belongs to the property changes, whp,
several times as $p=p(n)$ increases from $0$ to $1$.

  * •

Our main result, Theorem 1.1, shows that if ${\cal P}$ misses a bipartite
graph, then for $G=G(n,p)$ we have whp $\operatorname{ex}(G,{\cal
P})=o(n^{2})$. It would be interesting to provide a more accurate estimate for
this “bipartite” case. It seems plausible that in this case
$\operatorname{ex}(G,{\cal P})\leq n^{2-{\varepsilon}}$ for some
${\varepsilon}={\varepsilon}({\cal P})>0$.

  * •

The typical edit distance of a random graph from a hereditary property is very
different from the typical minimum number of edges that have to be deleted
from it to get a graph that belongs to the property. The latter quantity is
the one studied here, the former is treated, for example, in [3]. An example
illustrating the difference is that of the property of avoiding an induced
copy of a long even cycle $C_{2k}$. Theorem 1.1 shows that for, say, $p=1/2$,
whp one has to delete nearly all $(1/4+o(1))n^{2}$ edges of $G(n,1/2)$ to get
a subgraph that contains no induced copy of $C_{2k}$. On the other hand, since
the vertices of $C_{2k}$ cannot be covered by $k-1$ cliques it suffices, whp,
to add to $G(n,1/2)$ only $(1/4+o(1))n^{2}/(k-1)$ edges in order to cover all
its vertices by $k-1$ cliques, ensuring that the resulting graph will not
contain an induced copy of $C_{2k}$.

## Acknowledgment

The initial results in this note were obtained when the second author visited
the Department of Mathematics of Princeton University. He would like to thank
the department for the hospitality.

## References

  * [1] Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, and Gábor Simonyi, _Structured codes of graphs_ , SIAM J. Discrete Math., to appear.
  * [2] Noga Alon and Joel H. Spencer, _The probabilistic method_ , fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016.
  * [3] Noga Alon and Uri Stav, _What is the furthest graph from a hereditary property?_ , Random Structures Algorithms 33 (2008), no. 1, 87–104.
  * [4] David Conlon, Domingos Dellamonica, Steven La Fleur, Vojtěch Rödl, and Mathias Schacht, _A note on induced Ramsey numbers_ , A journey through discrete mathematics, Springer, Cham, 2017, pp. 357–366.
  * [5] David Conlon and William Timothy Gowers, _Combinatorial theorems in sparse random sets_ , Ann. of Math. (2) 184 (2016), no. 2, 367–454.
  * [6] David Conlon, William Timothy Gowers, Wojciech Samotij, and Mathias Schacht, _On the KŁR conjecture in random graphs_ , Israel J. Math. 203 (2014), no. 1, 535–580.
  * [7] Mathias Schacht, _Extremal results for random discrete structures_ , Ann. of Math. (2) 184 (2016), no. 2, 333–365.