# Programming Language Agnostic Mining of Code and Language Pairs with
Sequence Labeling Based Question Answering

Changran Hu1, Akshara Reddi Methukupalli2, Yutong Zhou2, Chen Wu3, Yubo Chen4
1University of California, Berkeley USA
2Tencent Cloud, Shanghai, China
3Department of Electronic Engineering, Tsinghua University, Beijing China
changran˙hu,akshara˙methukupalli,yutong˙zhou@berkeley.edu,chewu<EMAIL_ADDRESS>
###### Abstract.

Mining aligned natural language (NL) and programming language (PL) pairs is a
critical task to NL-PL understanding. Existing methods applied specialized
hand-crafted features or separately-trained models for each PL. However, they
usually suffered from low transferability across multiple PLs, especially for
niche PLs with less annotated data. Fortunately, a Stack Overflow answer post
is essentially a sequence of text and code blocks and its global textual
context can provide PL-agnostic supplementary information. In this paper, we
propose a Sequence Labeling based Question Answering (SLQA) method to mine NL-
PL pairs in a PL-agnostic manner. In particular, we propose to apply the BIO
tagging scheme instead of the conventional binary scheme to mine the code
solutions which are often composed of multiple blocks of a post. Experiments
on current single-PL single-block benchmarks and a manually-labeled cross-PL
multi-block benchmark prove the effectiveness and transferability of SLQA. We
further present a parallel NL-PL corpus named Lang2Code automatically mined
with SLQA, which contains about 1.4M pairs on 6 PLs. Under statistical
analysis and downstream evaluation, we demonstrate that Lang2Code is a large-
scale high-quality data resource for further NL-PL research.

##  1\. Introduction

Recent years, a new suite of developer assistance tools based on natural
language processing (NLP) have started to burgeon, such as code retrieval
(Allamanis et al., 2015; Wei and Ch, 2015; Husain et al., 2020), code
summarization (Allamanis et al., 2016; Iyer et al., 2016) and code synthesis
(Locascio et al., 2016; Desai et al., 2016; Quirk et al., 2015; Yin and
Neubig, 2017; Clement et al., 2020). Since data-driven methods have shown
great promise on these tasks (Yin et al., 2018), high-quality parallel natural
language (NL) and programming language (PL) corpora have gradually become
essential resources, making NL-PL pair mining a critical task for these
downstream applications.

Existing methods acquired the aligned NL-PL pairs through handcrafting
specialized features (Iyer et al., 2016; Yin et al., 2018) or training
separate models (Yao et al., 2018) for each PL. For example, Yin et al. (2018)
proposed to combine PL-specific handcrafted rules with neural network models.
Yao et al. (2018) proposed to incorporate the local textual context around
code blocks and train separate models for Python and SQL data. However, these
methods are highly dependent on large amounts of single-PL training data for
each PL, making it difficult to directly migrate them to niche PLs that lack
training data.

Figure 1. An example of a Stack Overflow answer post, which contains a NL
question title and a sequence of text and code blocks. The solution of this
post consists of the last two code blocks.

Fortunately, we observe that a Stack Overflow (SO) answer post is essentially
a sequence of text and code blocks. The global textual context of the post can
provide PL-agnostic supplementary information for mining correct code blocks
corresponding to the post’s NL title. For example, in Figure 1, even if we
remove the content of the code blocks, the remaining PL-agnostic context
“Given $\mathbb{C}_{1}$ and $\mathbb{C}_{2}$, start by … $\mathbb{C}_{3}$, now
let’s use … $\mathbb{C}_{4}$” still can help identify $\mathbb{C}_{3}$ and
$\mathbb{C}_{4}$ as the correct solution. This is quite similar to a question
answering task (Rajpurkar et al., 2016; Yang et al., 2018), which aims to
identify the correct answer of the given question from a textual context.

Inspired by the above observations, we propose a Sequence Labeling based
Question Answering (SLQA) method to mine NL-PL pairs in a PL-agnostic manner.
We first tokenize the text and code blocks of a post with a PL-independent
tokenizer, which eliminates the characteristics of the PL itself. Then we feed
the title and the converted content into a sequence tagger. The tagger assigns
a label to each code-block token to indicate whether it belongs to the answer.
Moreover, we observe that many solutions provided by SO posts are composed of
multiple code blocks interspersed with some explanatory text, as shown in
Figure 1. Therefore, we propose to apply the BIO tagging scheme (Ramshaw and
Marcus, 1995) to predict multiple code blocks as answers instead of the binary
scheme as in (Yao et al., 2018).

Finally, we present Lang2Code, a parallel NL-PL corpus automatically mined
with the SLQA model. The Lang2Code contains 1.4M NL-PL pairs over 6 PLs, which
is so far the largest NL-PL corpus with the broadest coverage of PLs to our
best knowledge. We also conduct a downstream evaluation on a NL-to-code
generation task, and the boosted performance by Lang2Code proves the high
quality of Lang2Code. The statistics and evaluation demonstrate that Lang2Code
is a large-scale and high-quality NL-PL corpus and can greatly help model
developments for tasks aiming to associate natural language with programming
language.

The main contribution of this paper are:

  * •

We propose the SLQA method to mine NL-PL pairs in a PL-agnostic manner.

  * •

We propose to apply the BIO tagging scheme instead of the previous binary
scheme to mine code solutions composed of multiple blocks.

  * •

We conduct experiments on the current single-PL single-block benchmarks and a
manually-annotated cross-PL multi-block benchmark, and the results demonstrate
the effectiveness and transferability of our method.

  * •

We further present Lang2Code, a large-scale and high-quality parallel NL-PL
corpus automatically mined with SLQA, containing about 1.4M NL-PL pairs over 6
PLs.

##  2\. Related Work

###  2.1. NL-PL Pair Mining

Existing methods for mining NL-PL pairs first proposed to utilize the
function’s code-documentation pairs because they are naturally aligned and can
be automatically mined from sources like GitHub. For example, Husain et al.
(2020) proposed the CodeSearchNet corpus by collecting function-level
documentations on the GitHub. Clement et al. (2020) proposed to translate
documentation strings to Python codes with transformers (Vaswani et al.,
2017). Feng et al. (2020) proposed the CodeBERT model which is pre-trained
with function-docstring pairs. However, language used in documentations is
fundamentally different from the general natural language. A function’s
documentation is often written by the same author of the code and therefore
does not provide much variability in terms of vocabulary (Husain et al.,
2020).

To address this issue, subsequent work focused on mining NL-PL pairs from
linguistically richer but unstructured code forums from sources like SO. For
example, Iyer et al. (2016) proposed a neural network to generate code
summaries with posts that has only one code block. Yin et al. (2018) proposed
to extract structured features to explore Python and Java forums and present
the automatically mined CoNaLa corpus. Yao et al. (2018) proposed a bi-view
hierarchical neural network and present the StaQC dataset. However, existing
methods usually required heavy PL-specific feature engineering or heavy PL-
specific data annotations. This poses great challenges for directly migrating
them across multiple PLs, especially for niche PLs which lack annotated data.
To overcome these drawbacks, we propose a PL-agnostic way to predict multiple
code blocks as a solution. We treat the code contents as natural language and
tokenize all the text and code blocks with a PL-independent tokenizer, which
eliminates the specific characteristics of the PLs. Then our model identifies
the correct solution(s) of the question by understanding the global PL-
agnostic textual context of the post.

###  2.2. NL Context Understanding

Recent progress of NLP techniques provided effective QA methods for
comprehending query-related NL context. For example, Seo et al. (2017)
proposed a BiDAF model to capture interactions between contexts and queries.
Devlin et al. (2019) and Liu et al. (2019) improved QA performance using pre-
trained language models. However, these conventional QA models usually
predicted only one contiguous answer span and are not suitable for answers
consisting of consecutive code blocks interspersed with text blocks. In
comparison, we propose to address this issue with the sequence labeling
mechanism (Lample et al., 2016). We assign a BIO tag (Ramshaw and Marcus,
1995) to each code block to indicate whether it belongs to the solution of the
question title. We elaborate on this method in Section 3.2.

Figure 2. The overall framework of SLQA and two variants: SLQA-text and SLQA-
code. The SLQA-code and SLQA models use code block contents as input. However,
the codes are tokenized with the same Byte-Pair Encoding (BPE) (Gage, 1994)
tokenizer as the NL context. This means that these two models are still PL-
agnostic.

##  3\. Preliminaries

In this section, we provide a task definition and describe how we annotated a
cross-PL multi-block dataset for model development.

###  3.1. Task Overview

Given a Stack Overflow question title and its answer post accepted by the
questioner, we aim at identifying all potential consecutive code blocks in the
accepted answer that can solve the question. The solutions may contain one
single code block or multiple code blocks interspersed with texts. Following
Yao et al. (2018), we focus on ”how-to-do-it” questions in SO, because their
answer posts are more likely to contain complete code solutions.

###  3.2. Manual Annotation

We first collected questions of six PLs from Stack Overflow’s raw data
dump111https://archive.org/details/stackexchange: Python, Java, SQL, R, Git
and Bash. Then we manually selected how-to questions by three annotators. We
kept the questions with accepted answers, and for each question we only kept
its title and the accepted answer post following (Yao et al., 2018). Next, we
annotated the standalone code blocks222We ignored in-line code blocks as our
pilot annotation study found that standalone blocks cover most of the
solutions. in the accepted answer with BIO tags. Specifically, we use the
following annotation protocol: (1) non-solution blocks are labeled as ”Outside
(O)”; (2) single-block solutions are labeled as ”Begin (B)”; (3) for multi-
block solutions, the first code block is labeled as ”B” and all subsequent
ones are labeled as ”Inside (I)”. This protocol was determined by three
annotators through annotating a unified set of sample data and running five
iterations of pilot study. The average Cohen’s kappa of the final iteration is
around 0.785. Finally, all data were exclusively divided to the three
annotators for annotation.

##  4\. Our Approach

The overall framework of our Sequence Labeling based Question Answering (SLQA)
approach is shown in Figure 2. First, we introduce the intuition in Section
4.1. Then we introduce the tokenizer and the token aggregator in Section 4.2.
Finally we introduce the sequence tagger in Section 4.3.

###  4.1. Intuition

Consider an answer post with question title $\mathbb{Q}$ and a sequence of
text and code blocks:
$\\{{\mathbb{T}_{1}},{\mathbb{C}_{1}},{\mathbb{T}_{2}},{\mathbb{C}_{2}}...{\mathbb{T}_{N}},{\mathbb{C}_{N}}\\}$,
where ${\mathbb{T}_{1:N}}$ and ${\mathbb{C}_{1:N}}$ denote the text and code
blocks, respectively. On one hand, we observe that the global textual context
of ${\mathbb{T}_{1:N}}$ can provide PL-independent information to identify the
solution. For example, in Figure 1, the words ”Given” and ”And” of the first
two text blocks $\\{\mathbb{T}_{1},\mathbb{T}_{2}\\}$ strongly indicate
$\\{\mathbb{C}_{1},\mathbb{C}_{2}\\}$ as prerequisites. Then the keywords
”Start by” and ”Now” of $\\{\mathbb{T}_{3},\mathbb{T}_{4}\\}$ suggest that
${\mathbb{C}_{3}}$ and ${\mathbb{C}_{4}}$ are the actual solution of the post.

On the other hand, the contents of the code blocks are intuitively
informative. However, previous work utilized PL-specific parsers to pre-
process the code (Yao et al., 2018), which is not suitable for cross-PL
transfer learning. To overcome this drawback, our full model SLQA incorporates
code contents by treating the code contents as natural language and using a
unified PL-agnostic tokenizer (Section 4.2) to process all text and code
blocks.

Surprisingly, we also discover that even without looking at the contents of
all the code blocks, the remaining textual context “Given $\mathbb{C}_{1}$ and
$\mathbb{C}_{2}$, start by … $\mathbb{C}_{3}$, now let’s use …
$\mathbb{C}_{4}$” still can help identify the solution. Therefore, we propose
a pure-text variant of SLQA, denoted as SLQA-text. Then another pure-code
variant SLQA-code is naturally proposed, which is useful to investigate the
effects of text and code separately, as shown in Figure 2.

###  4.2. Tokenizer and Token Aggregator

Given an answer post, we first use a unified tokenizer to tokenize the
question title, the text blocks, and the code blocks. However, the variance of
different PL’s keyword sets and the flexibility of the variables’ names may
lead to a large but sparse vocabulary. We apply a Byte-Pair Encoding (BPE)
(Gage, 1994) tokenizer to all blocks to alleviate data sparsity following (Liu
et al., 2019). We denote the output token sequences of $\mathbb{T}_{i}$,
$\mathbb{C}_{i}$ and $\mathbb{Q}$ as the italic symbols $T_{i}$, $C_{i}$ and
$Q$, respectively.

Then we aggregate the above tokens to construct the sequence tagger’s input
(Figure 2). First, we put $T_{1:N}$ and $C_{1:N}$ after $Q$ by the order of
appearance. Then, we insert two kinds of special tokens to the whole sequence:
(1) insert [SEP] after $Q$ to separate questions and contents (Devlin et al.,
2019); (2) insert[CB] and [/CB] around each $C_{i}$ to distinguish codes from
texts. For SLQA-code, we remove all text tokens $T_{*}$. For SLQA-text, we
remove all code tokens $C_{*}$ and [/CB]s, and left [CB]s as placeholders of
code blocks.

###  4.3. Sequence Taggers

Inspired by QA methods (Devlin et al., 2019; Liu et al., 2019), we use a pre-
trained language model to encode the input token sequence, such as RoBERTa
(Liu et al., 2019) in our model. We use its last hidden states
$\mathbf{h}^{S}_{1:M}$ as the token representations of the input sequence.
However, conventional QA models only predict the begin and end positions of a
contiguous token span as the correct answer, thus failed to predict multiple
code blocks interspersed with texts. For example, in Figure 2, the answer
tokens $C_{3}$ and $C_{4}$ are non-contiguous because the token span is cut
off by $T_{4}$ in the middle. To address this issue, we propose to apply the
sequence labeling method for answer prediction. We predict a BIO tag for each
[CB] token to find multiple consecutive code blocks as the solution, as shown
in Figure 2. Formally, we use a softmax classifier to predict the tag for the
$i$-th block ($i\in\\{1,2,\dots,N\\}$):

(1)
$\begin{split}p(\mathbf{y}_{i})&=\textrm{softmax}(\mathbf{W}\mathbf{h}_{m_{i}}^{S}+\mathbf{b})\\\
\textrm{tag}_{i}&=\arg\max_{k\in\\{B,I,O\\}}p(y_{i}=k)\end{split}$

where $(\mathbf{W},\mathbf{b})$ are the parameters of the classi, $m_{i}$
denotes the position of the $i$-th [CB] token. We train our model with a
cross-entropy loss function:

(2) $\mathcal{L}=-\frac{1}{N}\sum_{i=1}^{N}\log p(y_{i}=\hat{y}_{i})$

where $\hat{y}_{m_{i}}$ denotes the gold tag of the $i$-th block.

Note that Yao et al. (2018) also proposed to capture textual context for this
task. Our model essentially differs from theirs in that we apply a BIO tagging
scheme to find multi-block solutions, whereas their binary scheme could only
find single-block solutions. Moreover, we model the post content as a whole
sequence and capture its global textual context, while their methods only
incorporated the local textual context around the code blocks. We show that
the global textual context provides more information than the local context in
Section 5.4.

##  5\. Experiments

###  5.1. Datasets

We evaluate our methods on two datasets, which are referred to as StaQC-human
and Lang2Code-human in the following sections.

####  5.1.1. StaQC-human

StaQC (Yao et al., 2018) consists of 4,883 Python and 3,637 SQL manually
annotated question-code (QC) pairs. Each code block is annotated with 0 or 1
to indicate whether it solves the corresponding question. This means that
StaQC discards all multi-block joint solutions. The original training,
validation and test sets are split at the code block level and therefore not
applicable to our post-level approach. Moreover, two consecutive code blocks
from the same post may be placed into different subsets. Since they share the
same text block between them, this placement may cause potential data leakage.
Therefore, we reassemble the code blocks into posts and randomly split the
fully-annotated posts into new training, validation and test sets. Then we
transform the $\\{1,0\\}$ labels into $\\{B,O\\}$ tags. We denote the new
single-block dataset as StaQC-human. Table 1 shows the statistics of the
single-block StaQC-human dataset.

Table 1. Statistics of the StaQC-human dataset. Non. stands for non-solution blocks. Subset | Lang. | #Post | #Block
---|---|---|---
Single | Non.
Train | Python | 1,139 | 1,354 | 1,592
Valid | Python | 142 | 181 | 197
Test | Python | 143 | 164 | 204
Train | SQL | 1,056 | 1,632 | 1,016
Valid | SQL | 132 | 201 | 124
Test | SQL | 133 | 190 | 135

####  5.1.2. Lang2Code-human

Table 2. Statistics of the Lang2Code-human dataset. Multi. stands for code blocks that form multi-block solutions, and Non. stands for non-solution blocks. Subset | Lang. | #Post | #Block
---|---|---|---
Single | Multi. | Non.
Train | Python | 1,058 | 1,328 | 423 | 1,131
Valid | Python | 132 | 185 | 58 | 140
Test | Python | 133 | 178 | 44 | 149
Java | 53 | 47 | 68 | 23
SQL | 70 | 91 | 33 | 60
R | 80 | 88 | 44 | 84
Git | 75 | 63 | 107 | 41
Bash | 69 | 87 | 63 | 55

We construct the Lang2Code-human dataset with our manually-annotated data as
mentioned in Section 3.2. We focused on Python as the primary PL. The Python
posts are used as the training, validation sets and part of the test set. They
contain both randomly-sampled and hits-weighted sampled data to jointly
represent the distributions of all SO posts and the popular ones. Posts of
other five PLs (Java, SQL, R, Git, Bash) are randomly sampled and used as the
test set for cross-PL performance benchmarking. The statistics of the multi-
block Lang2Code-human dataset is shown in Table 2.

Table 3. Performance of SLQA and previous method on StaQC-human’s Python and SQL test sets. The best scores are in bold and the second-best scores are underlined. $\dagger$ denotes cross-PL performance. Method | Python | SQL
---|---|---
Train | Prec. | Rec. |  $F_{1}$. | Acc. | Train | Prec. | Rec. |  $F_{1}$. | Acc.
Select-First | Python | 64.3 | 56.1 | 59.9 | 66.6 | SQL | 73.7 | 51.3 | 60.5 | 60.6
Select-All | Python | 44.6 | 100 | 61.7 | 44.6 | SQL | 58.8 | 100 | 74.1 | 58.8
Text-HNN | Python | 71.7 | 79.5 | 75.4 | 76.8 | SQL | 76.5 | 86.6 | 81.2 | 76.5
Code-HNN | Python | 71.7 | 77.8 | 74.6 | 76.4 | SQL | 75.3 | 88.8 | 81.5 | 76.3
BiV-HNN | Python | 76.2 | 83.8 | 79.8 | 81.0 | SQL | 83.2 | 96.0 | 89.1 | 86.1
BiV-RoBERTa | Python | 75.8 | 76.1 | 75.9 | 77.7 | SQL | 82.9 | 91.1 | 86.8 | 83.4
SLQA-text | Python | 78.5 | 86.0 | 82.1 | 83.0 | SQL | 86.3 | 94.0 | 90.0 | 87.7
SLQA-code | Python | 72.8 | 87.0 | 79.3 | 79.1 | SQL | 84.2 | 89.0 | 86.5 | 83.5
SLQA | Python | 85.3 | 90.2 | 87.7 | 88.4 | SQL | 85.2 | 97.7 | 91.0 | 88.4
SLQA-text† | SQL | 74.6 | 90.1 | 81.6 | 81.9 | Python | 88.0 | 82.8 | 85.3 | 83.1
SLQA-code† | SQL | 84.5 | 24.3 | 37.7 | 63.6 | Python | 77.3 | 80.1 | 78.7 | 74.0
SLQA† | SQL | 79.5 | 82.3 | 80.9 | 82.3 | Python | 90.4 | 88.3 | 89.3 | 87.2

###  5.2. Experimental Settings

We tune the hyper-parameters on the validation sets with earlystopping
patience of 5. We load the pre-trained RoBERTa-Large
parameters333https://huggingface.co/roberta-large and fine-tune them during
training. We use the Adam (Kingma and Ba, 2014) optimizer to train our model
with the learning rate of $10^{-5}$ and 500 warmup steps. We set the weight
decay to $0.01$. We report the precision, recall and $F_{1}$ scores of the
predict solutions on both datasets. We also report the accuracy on StaQC-human
because of its binary labels. We train our model for five times with different
random seeds and report the average scores.

###  5.3. Baselines

We compare our model with the following baselines: (1) Select-All and Select-
First are two commonly used heuristics (Yao et al., 2018). Select-All treats
all code blocks in a post as standalone solutions, i.e., all code blocks are
labeled as ”B”. Select-First only chooses the first code block as the
standalone solution, which is equivalent to labeling the first code block as
”B” and the rest as ”O”. (2) BiV-HNN (Yao et al., 2018) learns the semantic
representation of a code block from token level to block level and
incorporates the local textual context around each code block. It has two main
variants, Text-HNN and Code-HNN, which discard code contents and textual
context, respectively. Although StaQC contains data of two PLs, these models
are not available for cross-PL experiments because they used PL-specific
vocabularies. Since StaQC-human is re-split at the post level, we re-train
BiV-HNN and its variants on StaQC-human with the official implementation and
report the post-level scores. (3) BiV-RoBERTa is similar to BiV-HNN, but uses
the RoBERTa instead of the HNN to capture the code contents and local textual
context (Figure 3).

Figure 3. The overall framework of BiV-HNN and BiV-RoBERTa. BiV-HNN is a GRU
based model that takes normalized code as input, where as BiV-RoBERTa is a
transformer based model takes raw code as input.

###  5.4. StaQC-human Results

We conduct single-PL and cross-PL experiments on StaQC-human Python dataset
and report the results in Table 3. From the results we have the following
observations:

Single-PL: (1) SLQA significantly outperforms previous Select-First, Select-
All and BiV-HNN methods. It indicates that our model can effectively capture
global textual context and code contents and improve the performance. (2) SLQA
outperforms the BiV-RoBERTa model. The two models use the same RoBERTa
encoder, the only difference is that SLQA uses global contextual information
while the other uses local contextual information. It indicates the
effectiveness of the global textual context for NL-PL understanding.
Additionally, BiV-RoBERTa performs worse than BiV-HNN. It shows that the PL-
specific code normalization (Figure 3) provides major contribution to the
performance. SLQA performs even better than BiV-HNN without code
normalization, which indicates that the improvements come primarily from the
global textual context rather than the pre-trained RoBERTa. (3) SLQA-text also
outperforms the BiV-HNN model. Since SLQA-text has no access to the code
contents but still brings improvements, this result further demonstrates the
effectiveness of our method to capture global textual information.

Table 4.  Performance of SLQA and heuristics on Lang2Code-human test set, including all the six PLs. The best scores are in bold and the second-best scores are underlined. Method | $F_{1}$
---|---
Python | Java | SQL | R | Git | Bash
Select-First | 49.8 | 37.5 | 40.2 | 45.2 | 30.2 | 41.3
Select-All | 63.4 | 44.1 | 63.7 | 54.5 | 41.1 | 55.9
SLQA-text | 69.7 | 53.8 | 70.0 | 64.0 | 55.4 | 65.8
SLQA-code | 70.6 | 50.0 | 59.8 | 64.7 | 48.0 | 61.5
SLQA | 75.7 | 62.9 | 76.1 | 66.5 | 58.7 | 70.1
Table 5.  The statistics of the Lang2Code corpus. #Solution Multi. refers to the number of NL-PL pairs that PL consists of multiple code blocks. #Blocks Multi. refers to the total number of code blocks combined in those NL-PL pairs that consist of multiple code blocks. Lang. | #Pairs | #Solutions | #Blocks
---|---|---|---
Single | Multi. | Single | Multi.
Python | 572,587 | 537,768 | 34,819 | 537,768 | 81,574
Java | 322,731 | 295,920 | 26,811 | 295,920 | 62,487
SQL | 234,939 | 226,548 | 8,391 | 226,548 | 19,040
R | 195,685 | 181,862 | 13,823 | 181,862 | 33,229
Git | 27,470 | 24,164 | 3,306 | 24,164 | 8,549
Bash | 45,099 | 43,104 | 1,995 | 43,104 | 4,801
Total | 1,398,511 | 1,309,366 | 89,145 | 1,309,366 | 209,680

Cross-PL: (1) SLQA-text achieves comparable results to the single-PL BiV-HNN
model. It indicates that the global textual context provides PL-agnostic
supplementary information and allows for transfer learning across different
PLs. (2) SLQA-code performs well on single-PL task but poorly on cross-PL
task, even worse than the heuristic baselines on the Python test set. It
validates the importance of textual information to cross-PL transfer learning.
(3) Cross-PL SLQA outperforms single-PL BiV-HNN and achieves comparable
results to single-PL SLQA-text. It indicates that our model can effectively
incorporate the code contents and textual context in a PL-agnostic manner and
improve the cross-PL transfer learning performance.

###  5.5. Lang2Code-human Results

We present the experimental results on the cross-PL multi-block Lang2Code
dataset in Table 4. We can observe that: (1) The SLQA scores on the Python
test set are significantly lower than StaQC-human’s single-PL scores. It
demonstrates that predicting multi-block solutions is a more challenging task
than predicting single-block solutions. (2) SLQA-code performs poorly on
cross-PL learning except for Python-to-R learning. It indicates that only
focusing on code contents is not effective enough for cross-PL learning
because the language styles varies greatly between different PLs, unless the
two PLs have similar styles like Python and R. (3) SLQA-text significantly
outperforms heuristic methods. It indicates that the global textual context
can provide critical PL-agnostic information to identify the correct solution
from an SO post. Our model effectively captures the global textual context and
improve the performance of cross-PL transfer learning. (4) The full SLQA model
significantly outperforms both the variants and the heuristics. It indicates
that SLQA effectively captures global textual context and code contents of a
post and allows for reliable transfer learning across multiple PLs.

##  6\. Lang2Code: An automatically mined NL-PL pairs dataset

In this section, we present Lang2Code, a large-scale and high-quality parallel
NL-PL corpus automatically mined using our SLQA model. It contains about 1.4M
NL-PL pairs over 6 PLs, as shown in Table 5. We will introduce the
construction pipeline in Section 6.1, the statistics in Section 6.2, and the
downstream evaluation of data quality in Section 6.3, respectively.

###  6.1. Construction Pipeline

Figure 4. The overall pipeline of automatically constructing the Lang2Code dataset. Figure 5. An illustration of the Lang2Code Corpus. In this SO post, two solutions corresponding to the question title were obtained, resulting in two NL-PL pairs. We include both the how-to likelihood and the BIO likelihoods in Lang2Code. Table 6. Overview of NL-PL datasets auto-mined from Stack Overflow. The largest size are in bold. Datasets | Python | Java | SQL | R | Git | Bash | C# | Total
---|---|---|---|---|---|---|---|---
CodeNN (Iyer et al., 2016) | / | / | 33k | / | / | / | 53k | 86k
StaQC (Yao et al., 2018) | 148k | 120k | / | / | / | / | / | 268k
SO-DS (Heyman and Cutsem, 2020a) | 12k | / | / | / | / | / | / | 12k
CoNaLa (Yin et al., 2018) | 601k | / | / | / | / | / | / | 601k
Lang2Code | 573k | 323k | 235k | 196k | 27k | 45k | / | 1399k

The overall pipeline is shown in Figure 4. In Section 3.2, we obtained 2,351
manually annotated tags from Lang2Code for the six languages, concomitant with
these tags are also binary labels indicating whether the question is a How-to
question. Using this data, we fine-tuned BERT 444https://huggingface.co/bert-
base-cased to train a binary classifier, obtaining 85.2% precision, 95.1%
recall and 89.9% $F_{1}$ score. Next we used this classifier with a threshold
of 0.5 to filter Stack Overflow posts pertaining to the six PLs we annotated
in Section 3.2. We filtered 1,000,888 single-block answer posts and 799,104
multi-block answer posts and kept 540,352 and 676,128 how-to questions
respectively. After that, for single-block answer posts, we follow previous
work (Iyer et al., 2016; Yin et al., 2018; Yao et al., 2018) to treat the only
code block as the solution to the question title. Thus we can have a NL-PL
pair out of each single-code answer posts. And for posts contain multiple code
blocks, we applied SLQA trained on Lang2Code-human to the question answer pair
and assigned BIO tags to every code blocks. As discussed in Section 3.2, using
BIO tags we can segregate multiple code-block solutions as the ones with ”B”
followed by one or more ”I” tags, whereas single code-block solutions are ones
with just a ”B” tag followed by ”O” tags or is the last code block. We pair
each code-block solution with the question title to construct an NL-PL pair.
For example, in Figure 5, We use Solution 1 and Solution 2 to pair with the
question title separately to obtain two NL-PL pairs.

###  6.2. Statistics of Lang2Code

We have mined 858,159 NL-PL pairs from multi-code answer posts, together with
the NL-PL pairs obtained from single-code answer posts, making a total of
1,398,511 NL-PL pairs in total. Table 5 presents the detailed statistics of
the Lang2Code corpus. To the best of our knowledge, this is the largest NL-PL
corpus mined from Stack Overflow so far, and the first corpus containing code
solutions that are composed of multiple code blocks. We will in the future
publish the Lang2Code corpus and open source all related code for future
research. Moreover, we compare the amount of data for each subset of
programming languages in the existing NL-PL datasets with Lang2Code. Table 6
shows the comparison results. From the results we can observe that Lang2Code
is the dataset with the broadest coverage of programming languages, and on
every PL language it collects more NL-PL pairs than previous datasets. In
addition, Lang2Code first presents Stack Overflow-based dataset on Git, R, and
Bash, which greatly helps develop data-hungry models for these niche PLs in
future NL-PL research.

###  6.3. Downstream Evaluation

To validate the data quality of the auto-mined Lang2Code corpus, we conduct a
downstream evaluation on a representative NL-to-code generation task (Xu et
al., 2020; Norouzi et al., 2021). The task is defined as translating a natural
language query (usually a description of a functionality) to corresponding
code snippet(s). For example, given the intent to “generate random integers
between 0 and 9”, one would expect the Python code snippet “import random;
random.randint(0, 9)”. The performance on this task represents the ability to
model the association between NL and PL. For evaluation purposes, we choose
the widely-used CoNaLa-human (Yin et al., 2018) as the benchmark dataset. It
covers real-world English queries about Python with diverse intents. The
dataset contains 2,179 training, 200 dev and 500 test human-annotated samples.
We use the same evaluation metric as the CoNaLa benchmark, corpus-level BLEU
calculated on target code outputs in the test set.

Table 7. Performance of CoNaLa, StaQC and Lang2Code pre-trained model on the code generation task. The best score is in bold. All the scores are produced without using the distribution sampling (Xu et al., 2020) and re-ranking techniques (Yin and Neubig, 2019). Method | BLEU
---|---
Man | 27.20
Man+CoNaLa-mined | 28.14
Man+StaQC-mined | 28.29
Man+Lang2Code-mined | 29.83
Man+Lang2Code-mined-clean | 30.68
Table 8. Examples of code snippets generated by models pre-trained with CoNaLa, StaQC, and Lang2Code. The italic comments are not generated by the models but added manually by authors. Intent | 1\. write line “Hello” to file “somefile.txt” |  | 2\. pandas: delete rows in dataframe “df” based on
---
multiple columns values
Gold |  | with open(’somefile.txt’, ’a’) as the_file:
---
the_file.write(’Hello\\\n’)
| df.set_index(list(’BC’))
---
.drop(tuples, errors=’ignore’)
.reset_index()
CoNaLa | f.write(’Hello’) |  df.drop([df], axis=1) # error, delete df itself
StaQC |  | with open ( ’somefile . txt ’, ’a’) as myfile:
---
myfile.write ( ’Hello’)
df.apply(lambda x:x.tolist(), axis=1)
Lang2Code |  | with open ( ’somefile . txt ’, ’a’) as f:
---
f.write ( ’Hello’)
df.drop(’str_2’, axis=1, inplace=True)

####  6.3.1. Baselines

Yin and Neubig (Yin and Neubig, 2018) proposed a transition based LSTM model
named TranX for this task. Furthermore, Xu et al. (Xu et al., 2020) proposed
to incorporate mined NL-PL pairs as external knowledge. Specifically, they
first pre-trained TranX on the top100k auto-mined CoNaLa NL-PL pairs (sorted
by confidence score). Then the model is fine-tuned on CoNaLa-human training
set, and finally evaluated on the CoNaLa-human test set. To investigate the
data quality of the auto-mined Lang2Code data, we conduct experiments of
replacing the mined CoNala pairs with StaQC (Yao et al., 2018) and Lang2Code
mined pairs. We compare the performance of the following settings:

  * •

Man: The model is solely trained with the CoNaLa-human training set without
pre-training.

  * •

Man+CoNaLa-Mined: The model is first pre-trained with top 100k mined CoNaLa
pairs, and then fine-tuned with the CoNaLa-human training set.

  * •

Man+StaQC-Mined: We replace the CoNaLa pre-train data with 100k StaQC mined
pairs. Since StaQC has no confidence score, we randomly sample 100k pairs from
the whole corpus.

  * •

Man+Lang2Code-Mined: We replace the CoNaLa pre-train data with top 100k
Lang2Code-mined pairs compared with Man+CoNaLa-Mined.

  * •

Man+Lang2Code-Mined-clean: Following CoNaLa’s pre-processing procedure, we
clean the top 100k Lang2Code mined pairs by removing the import statements
because they are considered as contexts rather than code snippets (Yin et al.,
2018). We also remove code snippets longer than 100 characters to avoid
distribution bias of code length. We pre-train the model with the cleaned
Lang2Code pairs and then fine-tune it with the CoNaLa-human training set.

####  6.3.2. Results

We report the BLEU scores of the five settings in Table 7. From the results we
can observe that pre-training with Lang2Code mined pairs significantly boosts
the performance. It indicates that our Lang2Code corpus contains less noise
and the data quality is higher than the mined CoNaLa and StaQC pairs. With
higher-quality pre-training data, the model is able to understand the
association between NL and PL more accurately.

####  6.3.3. Case Study

Table 8 shows the comparison of the models pre-trained with CoNaLa, StaQC and
Lang2Code mined pairs on two example intents. First, we can observe that the
CoNaLa model tends to generate short or incorrect code snippets compared with
the other two models. We hypothesize that this is because the code snippets in
CoNaLa are mined at the line level. Specifically, the CoNaLa code snippets
only contains 1.07 lines in average (Heyman and Cutsem, 2020b). In contrast,
the StaQC and Lang2Code’s block-level snippets contains 9.84 and 8.27 lines in
average, respectively. Therefore, for the CoNaLa pre-trained model, the
difficulty to generate multiple lines of code is greatly increased. Moreover,
short code snippets usually have incomplete function, which may lead to
generation results with obvious errors. This result indicates that CoNaLa
mined pairs are more likely to miss important code lines than StaQC and
Lang2Code, which is harmful to the downstream performance. Second, from the
second intent we observe that the model pre-trained on StaQC generates
semantically unrelated code snippets to the intent. We hypothesize that the
StaQC pairs are mined only using the local textual context around each code
block. In contrast, our Lang2Code pairs are mined with the global textual
context of the whole answer post. As mentioned in Section 5.4, the global
textual context is more effective than the local context in understanding the
association between NL and PL. This result indicates that the StaQC mined
pairs are more noisy than Lang2Code because the NL and PL within a pair are
less associated. The above results demonstrate the higher data quality of
Lang2Code than StaQC and CoNaLa, which is more beneficial to future NL-PL
research.

##  7\. Conclusion

In this paper, we propose a Sequence Labeling based Question Answering (SLQA)
approach to construct NL-PL pairs in a PL-agnostic way. We propose a model
that can produce multiple code blocks as solutions of a post’s question, which
is achieved by using BIO sequence tagging. We also propose to incorporate the
global textual context as PL-independent supplementary information. To
validate the capacity of our method, we manually annotate a challenging cross-
PL multi-block dataset, named Lang2Code-human. Substantial experiments on the
single-PL single-block StaQC-human and our Lang2Code-human benchmarks
demonstrate the effectiveness and cross-PL transferability of our method.
Finally, we present Lang2Code, the largest-to-date NL-PL corpus to the best of
our knowledge, containing over 1.4 million pairs spanning six PLs. Under
statistical analysis and downstream evaluation on code generation task, we
demonstrate that Lang2Code is a large-scale and high-quality NL-PL pair corpus
and can greatly help developing data-hungry models in future research.

## References

  * (1)
  * Allamanis et al. (2016) Miltiadis Allamanis, Hao Peng, and Charles Sutton. 2016\.  A Convolutional Attention Network for Extreme Summarization of Source Code.  arXiv:1602.03001 [cs.LG]
  * Allamanis et al. (2015) Miltos Allamanis, Daniel Tarlow, Andrew Gordon, and Yi Wei. 2015\.  Bimodal Modelling of Source Code and Natural Language. In _Proceedings of the 32nd International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 37)_ , Francis Bach and David Blei (Eds.). PMLR, Lille, France, 2123–2132.  http://proceedings.mlr.press/v37/allamanis15.html
  * Clement et al. (2020) Colin B. Clement, Dawn Drain, Jonathan Timcheck, Alexey Svyatkovskiy, and Neel Sundaresan. 2020\.  PyMT5: multi-mode translation of natural language and Python code with transformers.  arXiv:2010.03150 [cs.LG]
  * Desai et al. (2016) Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, and Subhajit Roy. 2016.  Program synthesis using natural language. In _Proceedings of the 38th International Conference on Software Engineering_. 345–356.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _NAACL-HLT_. 4171–4186.
  * 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.  arXiv:2002.08155 [cs.CL]
  * Gage (1994) Philip Gage. 1994\.  A New Algorithm for Data Compression.  _C Users J._ 12, 2 (Feb. 1994), 23–38.
  * Heyman and Cutsem (2020a) Geert Heyman and Tom Van Cutsem. 2020a.  Neural Code Search Revisited: Enhancing Code Snippet Retrieval through Natural Language Intent.  _CoRR_ abs/2008.12193 (2020).  arXiv:2008.12193 https://arxiv.org/abs/2008.12193
  * Heyman and Cutsem (2020b) Geert Heyman and Tom Van Cutsem. 2020b.  Neural Code Search Revisited: Enhancing Code Snippet Retrieval through Natural Language Intent.  arXiv:2008.12193 [cs.IR]
  * Husain et al. (2020) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt. 2020.  CodeSearchNet Challenge: Evaluating the State of Semantic Code Search.  arXiv:1909.09436 [cs.LG]
  * Iyer et al. (2016) Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2016.  Summarizing Source Code using a Neural Attention Model. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Berlin, Germany, 2073–2083.  https://doi.org/10.18653/v1/P16-1195
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016\.  Neural architectures for named entity recognition.  _arXiv preprint arXiv:1603.01360_ (2016).
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Locascio et al. (2016) Nicholas Locascio, Karthik Narasimhan, Eduardo DeLeon, Nate Kushman, and Regina Barzilay. 2016\.  Neural Generation of Regular Expressions from Natural Language with Minimal Domain Knowledge.  arXiv:1608.03000 [cs.CL]
  * Norouzi et al. (2021) Sajad Norouzi, Keyi Tang, and Yanshuai Cao. 2021.  Code Generation from Natural Language with Less Prior Knowledge and More Monolingual Data. In _ACL-IJCNLP_. 776–785.
  * Quirk et al. (2015) Chris Quirk, Raymond Mooney, and Michel Galley. 2015\.  Language to Code: Learning Semantic Parsers for If-This-Then-That Recipes. In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Association for Computational Linguistics, Beijing, China, 878–888.  https://doi.org/10.3115/v1/P15-1085
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ Questions for Machine Comprehension of Text.  arXiv:1606.05250 [cs.CL]
  * Ramshaw and Marcus (1995) Lance Ramshaw and Mitch Marcus. 1995.  Text Chunking using Transformation-Based Learning. In _Third Workshop on Very Large Corpora_.  https://www.aclweb.org/anthology/W95-0107
  * Seo et al. (2017) Min Joon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. 2017.  Bidirectional Attention Flow for Machine Comprehension.  (2017).  https://openreview.net/forum?id=HJ0UKP9ge
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _NIPS_. 6000–6010.
  * Wei and Ch (2015) Yi Wei and Nirupama Ch. 2015.  Building Bing Developer Assistant.
  * Xu et al. (2020) Frank F. Xu, Zhengbao Jiang, Pengcheng Yin, Bogdan Vasilescu, and Graham Neubig. 2020.  Incorporating External Knowledge through Pre-training for Natural Language to Code Generation.  _CoRR_ abs/2004.09015 (2020).  arXiv:2004.09015 https://arxiv.org/abs/2004.09015
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018\.  HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering.  arXiv:1809.09600 [cs.CL]
  * Yao et al. (2018) Ziyu Yao, Daniel S. Weld, Wei-Peng Chen, and Huan Sun. 2018\.  StaQC.  _Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW ’18_ (2018).  https://doi.org/10.1145/3178876.3186081
  * Yin et al. (2018) Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu, and Graham Neubig. 2018.  Learning to Mine Aligned Code and Natural Language Pairs from Stack Overflow.  arXiv:1805.08949 [cs.CL]
  * Yin and Neubig (2017) Pengcheng Yin and Graham Neubig. 2017.  A Syntactic Neural Model for General-Purpose Code Generation. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Vancouver, Canada, 440–450.  https://doi.org/10.18653/v1/P17-1041
  * Yin and Neubig (2018) Pengcheng Yin and Graham Neubig. 2018.  TRANX: A Transition-based Neural Abstract Syntax Parser for Semantic Parsing and Code Generation. In _EMNLP_. 7–12.
  * Yin and Neubig (2019) Pengcheng Yin and Graham Neubig. 2019.  Reranking for neural semantic parsing. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_.


# Quantitative stability estimate for an optimization problem under
constraints

H. Hajaiej

###### Abstract.

A class of functionals maximized by characteristic functions of balls is
identified by a mass transportation argument.

A variational approach to the study of standing waves for the nonlinear
Schrödinger equation leads to the minimization of functionals like

$\frac{1}{2}\int_{\mathbb{R}^{n}}|\nabla
u(x)|^{2}\,dx-\int_{\mathbb{R}^{n}}F(|x|,u(x))\,dx\,,$ (1)

over all $u\in H^{1}(\mathbb{R}^{n})$, $u\geq 0$, such that
$\int_{\mathbb{R}^{n}}u^{2}=1$, see [3] (here $n\in\mathbb{N},n\geq 1$). The
function $F$ describes the index of refraction of the media in which the wave
propagates. A typical example is

$F(r,s)=p(r)s^{2}+q(r)s^{d}\,,\quad 2<d<2+\frac{4}{n}\,,$

where $p$ and $q$ are positive decreasing functions, and the constraint on $d$
has to be assumed so to avoid non-existence issues due to unbalanced scalings.
The two terms of the energy (1) are in competition. Indeed, if we try to
maximize $\int_{\mathbb{R}^{n}}F(|x|,u(x))dx$ under the additional constraint
that $u\leq a$, then the unique maximizer is given by the function
$a\,1_{rB}$, having infinite Dirichlet integral (here $B$ is the Euclidean
unit ball and $r>0$ is such that $\int_{\mathbb{R}^{n}}(a\,1_{rB})^{2}=1$).

In this note we identify a simple sufficient condition on an integrand $F$
ensuring that $\int_{\mathbb{R}^{n}}F(|x|,u(x))dx$ presents this behavior.
More precisely, we are going to consider integrands
$F:\mathbb{R}^{+}\times\mathbb{R}^{+}\to\mathbb{R}^{+}$ (here
$\mathbb{R}^{+}:=[0,\infty)$), such that

  1. (H1)

for every $s\in\mathbb{R}^{+}$, $F(\cdot,s)$ is decreasing; for a.e.
$r\in\mathbb{R}^{+}$, $F(r,\cdot)$ is continuous on $\mathbb{R}^{+}$;

  2. (H2)

there exist $\alpha\in L^{1}(\mathbb{R}^{+},r^{n-1}dr)$ and a locally bounded
function $\beta:\mathbb{R}\to\mathbb{R}^{+}$ such that, for a.e.
$r\in\mathbb{R}^{+}$ and every $s\in\mathbb{R}^{+}$,
$F(r,s)\leq\alpha(r)\beta(s)$.

Given $a>0$ and $p\geq 1$, we consider the convex subset of
$L^{p}(\mathbb{R}^{n})$

$X:=\left\\{u\in L^{p}(\mathbb{R}^{n}):0\leq u\leq
a\,,\int_{\mathbb{R}^{n}}u^{p}\leq 1\right\\}\,,$

and define a functional ${\mathcal{F}}$ on $X$ by setting

$\displaystyle{\mathcal{F}}(u)=\int_{\mathbb{R}^{n}}F(|x|,u(x))dx\,,\quad\forall
u\in X\,.$

Note that, thanks to (H1) and (H2), $x\in\mathbb{R}^{n}\mapsto F(|x|,u(x))$ is
measurable and ${\mathcal{F}}(u)\in\mathbb{R}^{+}$ for every $u\in X$. We are
going to prove the following theorem:

######  Theorem 1.

Let $a>0$, $p\geq 1$, and let $F$ be such that (H1) and (H2) hold true. Assume
that there exists $t>0$ such that the ball
$E=\\{x\in\mathbb{R}^{n}:F(|x|,a)>t\\}$ satisfies $a^{p}|E|=1$, and that, for
a.e. $r\in\mathbb{R}^{+}$ and for every $\lambda\in[0,1]$,

$F(r,\lambda a)\leq\lambda^{p}F(r,a)\,.$ (2)

Then the function $w=a\,1_{E}$ is a maximum of ${\mathcal{F}}$ on $X$.
Moreover, if $F(\cdot,a)$ is strictly decreasing, then $w=a\,1_{E}$ is the
unique maximizer of ${\mathcal{F}}$ on $X$.

The proof of Theorem 1 is based on a basic result in mass transportation
theory, namely the Brenier Theorem [1] (see also [4]): given two Radon
measures $\mu_{1},\mu_{2}$ on $\mathbb{R}^{n}$, both absolutely continuous
with respect to the Lebesgue measure and such that
$\mu_{1}(\mathbb{R}^{n})=\mu_{2}(\mathbb{R}^{n})$, there exists a convex
function $\varphi:\mathbb{R}^{n}\to[0,\infty]$ and a Borel measurable map
$T:\mathbb{R}^{n}\to\mathbb{R}^{n}$ such that $T(x)=\nabla\varphi(x)$ at a.e.
$x\in\mathbb{R}^{n}$ and $T$ pushes forward $\mu_{1}$ into $\mu_{2}$, i.e.

$\int_{\mathbb{R}^{n}}H(y)d\mu_{2}(y)=\int_{\mathbb{R}^{n}}H(T(x))d\mu_{2}(x)\,,$
(3)

for every Borel function $H:\mathbb{R}^{n}\to[0,\infty]$. The mass
transportation approach to Theorem 1 allows also to deduce a quantitative
stability estimate on the maximality of $w=a1_{E}$, see Corollary 2 below. We
pass now to prove Theorem 1.

###### Proof of Theorem 1.

By (2), as $F(r,\cdot)$ is continuous for a.e. $r\in\mathbb{R}^{+}$, we deduce
that $F(r,0)=0$ for a.e. $r\in\mathbb{R}^{+}$. We let
$S^{n-1}=\\{x\in\mathbb{R}^{n}:|x|=1\\}$, and denote by $\sigma$ the
$(n-1)$-dimensional Hausdorff measure restricted to $S^{n-1}$.

Step one: Let us fix $u\in X$ and construct an auxiliary function $v=a\,1_{G}$
by letting

$G:=\left\\{x\in\mathbb{R}^{n}:|x|<\kappa\left(\frac{x}{|x|}\right)\right\\}\,,$

where we have introduced $\kappa:S^{n-1}\to\mathbb{R}^{+}$,

$\kappa(\nu):=\left(\frac{n}{a^{p}}\int_{0}^{\infty}u(r\nu)^{p}r^{n-1}dr\right)^{1/n}\,,\quad\nu\in
S^{n-1}\,.$ (4)

Note that $v(r\nu)=a\,1_{[0,\kappa(\nu)]}(r)$, and that the value of
$\kappa(\nu)$ has been chosen so that the measures

$1_{\mathbb{R}^{+}}(r)u(r\nu)^{p}\,r^{n-1}\,dr\,\quad\mbox{and}\quad
1_{\mathbb{R}^{+}}(r)v(r\nu)^{p}\,r^{n-1}\,dr\,,$

have the same total mass on $\mathbb{R}$. For every $\nu\in S^{n-1}$, let
$T_{\nu}$ denote the map given by Brenier theorem. By construction $T_{\nu}$
is increasing on $\mathbb{R}$, moreover, thanks to (3) we have

$\int_{\mathbb{R}^{+}}H(r)v(\nu
r)^{p}r^{n-1}dr=\int_{\mathbb{R}^{+}}H(T_{\nu}(r))u(\nu r)^{p}r^{n-1}dr\,,$
(5)

for every Borel function $H:\mathbb{R}\to[0,\infty]$: in particular
$T_{\nu}(r)\in[0,k(\nu)]$ for a.e. $r\in\mathbb{R}$. Note also that, as $0\leq
u\leq a$, we clearly have

$T_{\nu}(r)\leq r\,,\quad\mbox{for a.e. $r\in\mathbb{R}^{+}$.}$ (6)

We are going to prove that ${\mathcal{F}}(u)\leq{\mathcal{F}}(v)$. By (2) we
have that

$\displaystyle{\mathcal{F}}(u)=\int
d\sigma(\nu)\int_{\mathbb{R}^{+}}F(r,u(r\nu))r^{n-1}dr\leq\int
d\sigma(\nu)\int_{\mathbb{R}^{+}}\frac{F(r,a)}{a^{p}}u(r\nu)^{p}r^{n-1}dr\,,$
(7)

while at the same time, thanks to (5)

$\displaystyle{\mathcal{F}}(v)$ $\displaystyle=$ $\displaystyle\int
d\sigma(\nu)\int_{0}^{\kappa(\nu)}F(r,a)r^{n-1}dr=\int
d\sigma(\nu)\int_{\mathbb{R}^{+}}\frac{F(r,a)}{a^{p}}v(r\nu)^{p}r^{n-1}dr$
$\displaystyle=$ $\displaystyle\int
d\sigma(\nu)\int_{\mathbb{R}^{+}}\frac{F(T_{\nu}(r),a)}{a^{p}}u(r\nu)^{p}r^{n-1}dr\,,$

By (H1) and (6) it follows immediately that
${\mathcal{F}}(u)\leq{\mathcal{F}}(v)$.

Step two: We are going to prove that ${\mathcal{F}}(v)\leq{\mathcal{F}}(w)$.
We start by noticing that $|E|=|G|$. Indeed by (4)

$|G|=\int\frac{\kappa(\nu)^{n}}{n}\,d\sigma(\nu)=\frac{1}{a^{p}}\int_{\mathbb{R}^{n}}u^{p}=|E|\,.$

In particular $|E\setminus G|=|G\setminus E|$, and, without loss of
generality, $|E\setminus G|>0$. Consider the Brenier map
$T:\mathbb{R}^{n}\to\mathbb{R}^{n}$ between $1_{E\setminus G}(x)dx$ and
$1_{G\setminus E}(y)dy$. By (3),

$\int_{E\setminus G}H(y)dy=\int_{G\setminus E}H(T(x))dx\,,$ (8)

for every Borel function $H:\mathbb{R}^{n}\to[0,\infty]$. On choosing
$H(y)=F(y,a)$ we find

$\displaystyle\int_{E\setminus G}F(|x|,a)dx=\int_{G\setminus
E}F(|T(x)|,a)dx\,,$ (9)

while, on taking $H(y)=1_{E\setminus G}(y)$, we prove that $T(x)\in E\setminus
G$ for a.e. $x\in G\setminus E$. As $E$ is a ball, this last remark implies
that

$\displaystyle|T(x)|\leq|x|\,,\quad\mbox{for a.e. $x\in G\setminus E$\,.}$
(10)

On combining (10) with (9) we get

$\displaystyle{\mathcal{F}}(w)$ $\displaystyle=$ $\displaystyle\int_{G\cap
E}F(|x|,a)dx+\int_{E\setminus G}F(|x|,a)dx$ (11) $\displaystyle=$
$\displaystyle\int_{G\cap E}F(|x|,a)dx+\int_{G\setminus E}F(|T(x)|,a)dx$
$\displaystyle\geq$ $\displaystyle\int_{G\cap E}F(|x|,a)dx+\int_{G\setminus
E}F(|x|,a)dx={\mathcal{F}}(v)\,,$

and the conclusion follows.

Let us now assume that for every $s\in\mathbb{R}^{+}$ the function
$F(\cdot,a)$ is strictly decreasing, and consider a function $u\in X$ that
maximizes ${\mathcal{F}}$ on $X$, i.e. such that
${\mathcal{F}}(u)={\mathcal{F}}(w)$. We want to show that $u=w$ a.e. on
$\mathbb{R}^{n}$. Let us prove that $G=E$ up to null sets. Indeed, let $R$
denote the radius of the ball $E$. If $|G\setminus E|>0$, then we can consider
$T$ and repeat the above argument. Since $F(\cdot,a)$ is strictly decreasing
and equality holds in (11), we find that $|T(x)|=|x|$ for a.e. $x\in
G\setminus E$. Thus $|T(x)|\geq R$ for a.e. $x\in\mathbb{R}$; but $T(x)\in
E\setminus G$ for a.e. $x\in G\setminus E$, therefore it must be $|G\setminus
E|=0$, a contradiction. As $G=E$ up to null sets, we have $\kappa(\nu)=R$ for
every $\nu\in S^{n-1}$. The equality sign in (7) implies that, for
$\sigma$-a.e. $\nu\in S^{n-1}$, $T_{\nu}(r)=r$ for a.e. $r\in\\{t:u(\nu
t)>0\\}$. As $0\leq T_{\nu}\leq\kappa(\nu)=R$, by (5) and (6) we deduce that
$\\{t:u(\nu t)>0\\}\subset[0,R]$ for $\sigma$-a.e. $\nu\in S^{n-1}$. On
applying (5) to $H=1_{\\{t:u(\nu t)>0\\}}$ we deduce $u(\nu r)=a$ on
$\\{t:u(\nu t)>0\\}$, therefore that $u(\nu r)=a\,1_{[0,R]}(r)$. In particular
$u=w$ a.e. on $\mathbb{R}^{n}$. ∎

We come now to a quantitative stability estimate:

######  Corollary 2.

Under the assumptions of Theorem 1, let us assume the existence of $\lambda>0$
such that, whenever $0<r_{1}<r_{2}$,

$F(r_{1},a)\geq F(r_{2},a)+\lambda(r_{2}-r_{1})\,.$ (12)

Then, for every $u\in X$ we have that

$\int_{\mathbb{R}^{n}}|u-w|^{p}\leq
C(n,p,a)\sqrt{\frac{{\mathcal{F}}(w)-{\mathcal{F}}(u)}{\lambda}}\,.$ (13)

where $C(n,p,a)$ is a constant depending only on $n$, $p$ and $a$.

###### Proof.

Let $\delta:={\mathcal{F}}(w)-{\mathcal{F}}(u)$. Thanks to (12), from (7) and
(11) we find that

$\displaystyle\delta$ $\displaystyle\geq$
$\displaystyle\lambda\int_{G\setminus E}(|x|-|T(x)|)dx\,,$ (14)
$\displaystyle\delta$ $\displaystyle\geq$ $\displaystyle\lambda\int
d\sigma(\nu)\int_{0}^{\infty}(r-T_{\nu}(r))\frac{u(r\nu)^{p}}{a^{p}}r^{n-1}dr\,.$
(15)

We now consider (14) and (15) separately:

Step one: Let $\varepsilon\in(0,R)$, then $(R+\varepsilon)^{n}\leq
R^{n}+c(n)R^{n-1}\varepsilon$. Thus

$\displaystyle\frac{1}{a^{p}}\int_{\mathbb{R}^{n}}|w-v|^{p}$ $\displaystyle=$
$\displaystyle|E\Delta G|=2|G\setminus E|\leq 2\\{|G\setminus
B_{R+\varepsilon}|+|B_{R+\varepsilon}\setminus B_{R}|\\}$ $\displaystyle\leq$
$\displaystyle C(n)\left\\{|G\setminus B_{R+\varepsilon}|+\varepsilon
R^{n-1}\right\\}\,.$

If $x\in G\setminus B_{R+\varepsilon}$ then $|x|\geq
R+\varepsilon\geq|T(x)|+\varepsilon$. By (14) we have $|G\setminus
B_{R+\varepsilon}|\leq(\delta/\varepsilon\lambda)$, therefore we come to

$\frac{1}{a^{p}}\int_{\mathbb{R}^{n}}|w-v|^{p}\leq
C(n)\left\\{\frac{\delta}{\lambda\varepsilon}+\varepsilon R^{n-1}\right\\}\,.$

We minimize over $\varepsilon\in[0,R]$ and find

$\frac{1}{a^{p}}\int_{\mathbb{R}^{n}}|w-v|^{p}\leq
C(n)\max\left\\{\sqrt{\frac{\delta R^{n-1}}{\lambda}},\frac{\delta}{\lambda
R}\right\\}\,.$ (16)

Step two: We start by noticing that

$\displaystyle\int_{\mathbb{R}^{n}}|u-v|^{p}$ $\displaystyle=$
$\displaystyle\int_{G}(a-u)^{p}+\int_{\mathbb{R}^{n}\setminus
G}u^{p}\leq\int_{G}(a^{p}-u^{p})+\int_{\mathbb{R}^{n}\setminus
G}u^{p}=2\int_{\mathbb{R}^{n}\setminus G}u^{p}$ $\displaystyle=$
$\displaystyle 2\int\tau_{2}(\nu)d\sigma(\nu)\,,$

where, for every $\nu\in S^{n-1}$, we have set

$\tau_{1}(\nu):=\int_{0}^{\kappa(\nu)}u(r\nu)^{p}r^{n-1}dr\,,\quad\tau_{2}(\nu):=\int_{\kappa(\nu)}^{\infty}u(r\nu)^{p}r^{n-1}dr\,.$

Since $a^{p}\kappa(\nu)^{n}/n=\tau_{1}(\nu)+\tau_{2}(\nu)$, we have that

$\displaystyle a^{p}\frac{T_{\nu}(r)^{n}}{n}$ $\displaystyle\leq$
$\displaystyle\tau_{1}(\nu)+\int_{\kappa(\nu)}^{r}u(t\nu)t^{n-1}dt\leq\tau_{1}(\nu)+a^{p}\frac{r^{n}}{n}-a^{p}\frac{\kappa(\nu)^{n}}{n}\,,$

for every $r\geq\kappa(\nu)$, i.e.,

$T_{\nu}(r)\leq\left(r^{n}-\frac{n\tau_{2}(\nu)}{a^{p}}\right)^{1/n}\,,\quad\forall
r\geq\kappa(\nu)\,.$

Then by (15) we deduce that

$\displaystyle\frac{\delta}{\lambda}$ $\displaystyle\geq$ $\displaystyle\int
d\sigma(\nu)\int_{\kappa(\nu)}^{\infty}\left[r-\left(r^{n}-\frac{n\tau_{2}(\nu)}{a^{p}}\right)^{1/n}\right]u(r\nu)^{p}r^{n-1}dr$
$\displaystyle\geq$ $\displaystyle\int
d\sigma(\nu)\int_{\kappa(\nu)}^{\infty}\frac{\tau_{2}(\nu)}{a^{p}}\left(r^{n}-\frac{n\tau_{2}(\nu)}{a^{p}}\right)^{(1/n)-1}u(r\nu)^{p}r^{n-1}dr$
$\displaystyle\geq$
$\displaystyle\int\frac{\tau_{2}(\nu)^{2}}{a^{p}}\left(\kappa(\nu)^{n}-\frac{n\tau_{2}(\nu)}{a^{p}}\right)^{(1/n)-1}d\sigma(\nu)$
$\displaystyle=$
$\displaystyle\frac{c(n)}{a^{p/n}}\int\tau_{2}(\nu)^{2}\tau_{1}(\nu)^{(1/n)-1}d\sigma(\nu)\,.$

By Hölder inequality

$\displaystyle\int_{\mathbb{R}^{n}}|u-v|^{p}\leq
2\int\tau_{2}(\nu)d\sigma(\nu)\leq
C(n)\sqrt{a^{p/n}\frac{\delta}{\lambda}}\sqrt{\int\tau_{1}(\nu)^{1-(1/n)}d\sigma(\nu)}\,.$

By Jensen inequality for concave functions,

$\displaystyle\int\tau_{1}(\nu)^{1-(1/n)}d\sigma(\nu)$ $\displaystyle\leq$
$\displaystyle C(n)\left(\int\tau_{1}(\nu)d\sigma(\nu)\right)^{1-(1/n)}$
$\displaystyle\leq$ $\displaystyle C(n)\left(\int
a^{p}\frac{\kappa(\nu)^{n}}{n}d\sigma(\nu)\right)^{1-(1/n)}=C(n)\,,$

and we come to conclude that

$\int_{\mathbb{R}^{n}}|u-v|^{p}\leq C(n)\sqrt{a^{p/n}\frac{\delta}{\lambda}}$
(17)

Step three: As $\int|w-u|^{p}\leq 2^{p}$, (13) follows trivially whenever
$\delta\geq\leq$. Let us now assume that $\delta\leq\lambda$, then (13) is
easily deduced from (16) and (17). ∎

## References

  * [1] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (4) (1991) 375–417.
  * [2] C. Draghici & H. Hajaiej, Uniqueness and characterization of maximizers of integral functionals with constraints, preprint.
  * [3] H. Hajaiej & C. A. Stuart, On the variational approach to the stability of standing waves for the nonlinear Schrödinger equation. Adv. Nonlinear Stud. 4 (2004), no. 4, 469–501.
  * [4] R.J. McCann, Existence and uniqueness of monotone measure-preserving maps, Duke Math. J. 80 (2) (1995) 309–323.
  * [5] R.J. McCann, A convexity principle for interacting gases, Adv. Math. 128 (1) (1997) 153–179.