# Revisiting Iterative Back-Translation from the Perspective of Compositional
Generalization

Yinuo Guo1 , Hualei Zhu2∗, Zeqi Lin3, Bei Chen3, Jian-Guang Lou3, Dongmei
Zhang3
Work done during an internship at Microsoft Research Asia. The first two
authors contributed equally.

###### Abstract

Human intelligence exhibits compositional generalization (i.e., the capacity
to understand and produce unseen combinations of seen components), but current
neural seq2seq models lack such ability. In this paper, we revisit _iterative
back-translation_ , a simple yet effective semi-supervised method, to
investigate whether and how it can improve compositional generalization. In
this work: (1) We first empirically show that iterative back-translation
substantially improves the performance on compositional generalization
benchmarks (CFQ and SCAN). (2) To understand why iterative back-translation is
useful, we carefully examine the performance gains and find that iterative
back-translation can increasingly correct errors in pseudo-parallel data. (3)
To further encourage this mechanism, we propose _curriculum iterative back-
translation_ , which better improves the quality of pseudo-parallel data, thus
further improving the performance.

##  1 Introduction

Human intelligence exhibits _compositional generalization_ , the ability to
understand and produce unseen combinations of seen components (Chomsky 1965;
Fodor and Pylyshyn 1988). For example, if a person knows the meaning of “run”
and “run twice”, once she learns the meaning of a new word “jump”, she can
immediately understand the meaning of “jump twice”. This compositional
generalization is essential in human cognition, enabling humans to learn
semantics from very limited data and extend to unseen data (Montague 1974;
Partee 1984; Lake et al. 2017). Therefore, it is widely believed that
compositional generalization is a key property towards human-like AI (Mikolov,
Joulin, and Baroni 2016; Bengio 2019; Mollica et al. 2020). However, in recent
years, accumulating evidences have shown that neural sequence-to-sequence
(seq2seq) models exhibit limited compositional generalization ability (Lake
and Baroni 2018; Hupkes et al. 2020; Keysers et al. 2020; Furrer et al. 2020).

On the other hand, semi-supervised learning (Chapelle, Scholkopf, and Zien
2009) is a machine learning paradigm that alleviates the limited-data problem
through exploiting a large amount of unlabelled data, which has been
successfully used in many different areas such as machine translation
(Sennrich, Haddow, and Birch 2016; He et al. 2016; Skorokhodov et al. 2018)
and semantic parsing (Yin et al. 2018; Cao et al. 2019). In sequence-to-
sequence (seq2seq) tasks, unlabelled data (i.e., monolingual data) are usually
cheap and abundant, containing a large amount of combinations that are unseen
in limited labelled data (i.e., parallel data). Therefore, we propose a
hypothesis that _semi-supervised learning can enable seq2seq models understand
and produce much more combinations beyond labelled data, thus tackling the
bottleneck of lacking compositional generalization_. If this hypothesis holds
true, the lack of compositional generalization would no longer be a bottleneck
of seq2seq models, as we can simply tackle it through exploiting large-scale
monolingual data with diverse combinations.

In this work, we focus on _Iterative Back-Translation (IBT)_ (Hoang et al.
2018), a simple yet effective semi-supervised method that has been
successfully applied in machine translation. The key idea behind it is to
iteratively augment original parallel training data with pseudo-parallel data
generated from monolingual data. To our best knowledge, iterative back-
translation has not been studied extensively from the perspective of
compositional generalization. This is partially because a concern about _the
quality of pseudo-parallel data_ : due to the problem of lacking compositional
generalization, for non-parallel data with unseen combinations beyond the
parallel training data, pseudo-parallel data generated from them will be
error-prone. It is natural to speculate that errors in pseudo-parallel data
are going to be reinforced and then even harm the performance.

This paper broadens the understanding of iterative back-translation from the
perspective of compositional generalization, through answering three research
questions: RQ1.  How does iterative back-translation affect neural seq2seq
models’ ability to generalize to more combinations beyond parallel data? RQ2.
If iterative back-translation is useful from the perspective of compositional
generalization, what is the key that contributes to its success? RQ3.  Is
there a way to further improve the quality of pseudo-parallel data, thereby
further improving the performance?

Main Contributions. (1) We empirically show that iterative back-translation
substantially improves the performance on compositional generalization
benchmarks (CFQ and SCAN) (Section 3). (2) To understand what contributes to
its success, we carefully examine the performance gains and observe that
iterative back-translation is effective to correct errors in pseudo-parallel
data (Section 4). (3) Motivated by this analysis, we propose _curriculum
iterative back-translation_ to further improve the quality of pseudo-parallel
data, thereby improving the performance of iterative back-translation (Section
5).

##  2 Background

###  2.1 Compositional Generalization Benchmarks

In recent years, the compositional generalization ability of DNN models has
become a hot research problem in artificial intelligence, especially in
Natural Language Understanding (NLU), because compositional generalization
ability has been recognized as a basic but essential capability of human
intelligence (Lake et al. 2017). Two benchmarks, SCAN (Lake and Baroni 2018)
and CFQ (Keysers et al. 2020), have been proposed for measuring the
compositional generalization ability of different machine learning-based NLU
systems. Our experiments are also conducted on these two benchmarks.

#### SCAN

The SCAN dataset consists of input natural language commands (e.g., “ _jump
and look left twice_ ”) paired with output action sequences (e.g., “ _JUMP
LTURN LOOK LTURN LOOK_ ”). Difficult tasks are proposed based on different
data split settings, e.g., (1) ADD_JUMP: the pairs of train and test are split
in terms of the primitive _JUMP_. The train set consists of _(jump, JUMP)_ and
all pairs without the primitive _JUMP_. The rest forms the test set. (2)
LENGTH: Pairs are split by action sequence length into train set ($\leq 22$
tokens) and test set ($\geq 24$ tokens). (3) AROUND_RIGHT: The phrase “
_around right_ ” is held out from the train set, while “around” and “right”
appear separately. (4) OPPOSITE_RIGHT: This task is similar to AROUND_RIGHT,
while the held-out phrase is “ _opposite right_ ”.

#### CFQ

The _Complex Freebase Questions (CFQ)_ benchmark (Keysers et al. 2020)
contains input natural language questions paired with their output meaning
representations (SPARQL queries against the Freebase knowledge graph). To
comprehensively measure a learner’s compositional generalization ability, CFQ
dataset is splitted into train and test sets based on two principles: (1)
_Minimizing primitive divergence_ : all primitives present in the test set are
also present in the training set, and the distribution of primitives in the
training set is as similar as possible to their distribution in the test set.
(2) _Maximizing compound divergence_ : the distribution of compounds (i.e.,
logical substructures in SPARQL queries) in the training set is as different
as possible from the distribution in the test set. The second principle
guarantees that the task is compositionally challenging. Following these two
principles, three different _maximum compound divergence (MCD)_ dataset splits
are constructed. The mean accuracy of standard neural seq2seq models on the
MCD splits is below 20%. Moreover, this benchmark also constructs 3 MCD data
splits for SCAN dataset, and the mean accuracy of standard neural seq2seq
models is about 4%.

Figure 1: Iterative back-translation: exploiting monolingual data to augment
parallel training data. The solid lines mean that the src2trg/trg2src model
generates pseudo-parallel data from monolingual data; the dashed lines mean
that parallel and pseudo-parallel data are used to train the models.

###  2.2 Iterative Back-Translation (IBT)

Iterative back-translation (Hoang et al. 2018) has been proved as an effective
method utilizing bi-directional monolingual data to improve the performance of
machine translation models. Algorithm 1 describes the training process of
iterative back-translation. Firstly, the source-to-target (src2trg) model and
target-to-source (trg2src) model are initially trained on the original
parallel data ($D_{p}$) for $K$ steps (Line 1). After this initial stage, each
training step samples a batch of monolingual data from one direction and back-
translate them to the other direction. Then it would perform two mini-batches
to train source-to-target model using the given parallel data and pseudo
backtranslated parallel data separately, and also another two mini-batches for
training target-to-source model. Figure 1 visualizes the iterative training
process.

Algorithm 1 Iterative Back-Translation

Input: parallel data $D_{p}$, monolingual data $D_{src}$, $D_{trg}$
Output: source-to-target model $M_{\rightarrow}$ and target-to-source model
$M_{\leftarrow}$

1:Initial Stage: Separately train source-to-target model $M_{\rightarrow}$ and
target-to-source model $M_{\leftarrow}$ on $D_{p}$ for K steps

2:while $M_{\rightarrow}$ and $M_{\leftarrow}$ have not converged or step
$\leq$ N do

3: Sample a batch $B_{t}$ from $D_{trg}$ and use $M_{\leftarrow}$ to create
$B_{p}=\\{(\hat{s},t)|t\in B_{t}\\}$

4: Sample a batch $B_{s}$ from $D_{src}$ and use $M_{\rightarrow}$ to create
$B_{p}^{\prime}=\\{(s,\hat{t})|s\in B_{s}\\}$

5: Train source-to-target model $M_{\rightarrow}$ on $D_{p}$

6: Train source-to-target model $M_{\rightarrow}$ on $B_{p}$

7: Train target-to-source model $M_{\leftarrow}$ on $D_{p}$

8: Train target-to-source model $M_{\leftarrow}$ on $B_{p}^{\prime}$

9:end while

Table 1: Performance (accuracy) on SCAN Tasks. Cells with a white background are results obtained in previous papers; cells with a grey background are results obtained in this paper. Models | ADD_JUMP | LENGTH | AROUND_RIGHT | OPPOSITE_RIGHT | MCD1 | MCD2 | MCD3
---|---|---|---|---|---|---|---
LSTM+Att | $0.0\pm 0.0$ | $14.1$ | $0.0\pm 0.0$ | $16.5\pm 6.4$ | $6.5\pm 3.0$ | $4.2\pm 1.4$ | $1.4\pm 0.2$
Transformer | $1.0\pm 0.6$ | $0.0$ | $53.3\pm 10.9$ | $3.0\pm 6.8$ | $0.4\pm 0.2$ | $1.6\pm 0.3$ | $0.88\pm 0.4$
Uni-Transformer | $0.3\pm 0.3$ | $0.0$ | $47.0\pm 10.0$ | 15.2$\pm$13.0 | $0.5\pm 0.1$ | $1.5\pm 0.2$ | $1.1\pm 0.4$
Syn-att | $91.0\pm 27.4$ | $15.2\pm 0.7$ | $28.9\pm 34.8$ | $10.5\pm 8.8$ | - | - | -
CGPS | $98.8\pm 1.4$ | $20.3\pm 1.1$ | $83.2\pm 13.2$ | $89.3\pm 15.5$ | $1.2\pm 1.0$ | $1.7\pm 2.0$ | $0.6\pm 0.3$
Equivariant | $99.1\pm 0.0$ | $15.9\pm 3.2$ | $\mathbf{92.0\pm 0.2}$ | - | - | - | -
GECA | $87.0$ | - | $82.0$ | - | - | - | -
Meta-seq2seq | $99.9$ | $99.9$ | $16.6$ | - | - | - | -
T5-11B | $98.3$ | $3.3$ | $49.2$ | $\mathbf{99.1}$ | $7.9$ | $2.4$ | $16.8$
GRU+Att (Ours) | $0.6$ | $14.3$ | $23.8$ | $0.27$ | $18.7$ | $32.0$ | $42.4$
+mono30 | $\mathbf{99.6}$ | $\mathbf{77.7}$ | $37.8$ | $95.8$ | $\mathbf{64.3}$ | $\mathbf{80.8}$ | $\mathbf{52.2}$
+mono100 | $100.0$ | $99.9$ | $42.9$ | $100.0$ | $87.1$ | $99.0$ | $64.7$
+transductive | $100.0$ | $99.3$ | $34.5$ | $100.0$ | $74.8$ | $99.7$ | $77.4$

##  3 IBT for Compositional Generalization

To examine the effectiveness of IBT for compositional generalization, we
conduct a series of experiments on two compositional generalization benchmarks
(SCAN and CFQ, introduced in Section 2.1).

###  3.1 Setup

#### Monolingual Data Settings

In our experiments, we conduct different monolingual data settings as follows:

  * •

+transductive: _use all test data as monolingual data._ We use this setting to
explore how iterative back-translation performs with the most ideal
monolingual data.

  * •

+mono100: _use all dev data as monolingual data._ In this setting, test data
do not appear in the monolingual data, while the monolingual data contains
much more unseen combinations beyond the parallel training data.

  * •

+mono30: _randomly sample 30% source sequences and 30% target sequences from
dev data._ This setting is more realistic than “+tranductive” and “+mono100”,
because there is no implicit correspondence between source-side and target-
side monolingual data (i.e., for a sequence in source-side monolingual data,
the target-side monolingual data do not necessarily contain its corresponding
target sequence, and vice versa). Therefore, in our analysis of experimental
results, we regard results of “+mono30” as the actual performance of iterative
back-translation.

Note that because there are no dev data in SCAN tasks, we randomly hold out
half of the original test data as the dev data (the held-out dev data and the
remaining test data are not overlapped).

#### Implementation Details

We implement iterative back-translation based on the code of
UNdreaMT111https://github.com/artetxem/undreamt (Artetxe et al. 2018). For
CFQ, we use a 2-layer GRU encoder-decoder model equipped with attention. We
set the size of both word embedding and hidden states to 300. We use a dropout
layer with the rate of 0.5 and the training process lasts 30000 iterations
with batch size 128. For SCAN, we also use a 2-layer GRU encoder-decoder model
with attention. Both of the embedding size and hidden size are set to 200. We
use a dropout layer with the rate of 0.5 and the training process lasts 35000
iterations with batch size 64. We set $K=5000$ steps in Algorithm 1 for both
CFQ and SCAN benchmarks.

#### Baselines

(i) General seq2seq models: LSTM, Transformer and Uni-Transformer (Keysers et
al. 2020). (ii) SOTA models on SCAN/CFQ benchmarks: Syn-att (Russin et al.
2019), CGPS (Li et al. 2019), Equivariant (Gordon et al. 2019), GECA (Andreas
2020), Meta-seq2seq (Lake 2019) and T5-11B (Furrer et al. 2020).

Table 2: Performance (accuracy) on CFQ tasks. Models | MCD1 | MCD2 | MCD3
---|---|---|---
LSTM+Attn | $28.9\pm 1.8$ | $5.0\pm 0.8$ | $10.8\pm 0.6$
Transformer | $34.9\pm 1.1$ | $8.2\pm 0.3$ | $10.6\pm 1.1$
Uni-Transformer | $37.4\pm 2.2$ | $8.1\pm 1.6$ | $11.3\pm 0.3$
CGPS | $13.2\pm 3.9$ | $1.6\pm 0.8$ | $6.6\pm 0.6$
T5-11B | $61.4\pm 4.8$ | $30.1\pm 2.2$ | $31.2\pm 5.7$
GRU+Attn (Ours) | $32.6\pm 0.22$ | $6.0\pm 0.25$ | $9.5\pm 0.25$
+mono30 | $\mathbf{64.8\pm 4.4}$ | $\mathbf{57.8\pm 4.9}$ | $\mathbf{64.6\pm 4.9}$
+mono100 | $83.2\pm 3.1$ | $71.5\pm 6.9$ | $81.3\pm 1.6$
+transductive | $88.4\pm 0.7$ | $81.6\pm 6.5$ | $88.2\pm 2.2$

###  3.2 Observations

Figure 2: Quality (accuracy scores) of generated target data during the
training procedure. Figure 3: Quality (BLEU scores) of generated source data
during the training procedure.

We report the experimental results in Table 1 (SCAN) and 2 (CFQ). Notice that
we pay more attention to MCD splits (on both SCAN and CFQ), since it has been
proven that they are more comprehensive for evaluating compositional
generalization than other splits (Keysers et al. 2020; Furrer et al. 2020).
Our observations are as follows:

1.Iterative Back-translation substantially improves the performance on
compositional generalization benchmarks. Firstly, IBT can always bring large
performance gains to our baseline (GRU+Att). Then, compared to the previous
state-of-the-art models, IBT can consistently achieve remarkable performance
on all tasks, while those SOTA models only show impressive performances on
ADD_JUMP / LENGTH / AROUND_RIGHT / OPPOSITE_RIGHT tasks of SCAN, but perform
poorly on MCD tasks of SCAN/CFQ. Moreover, IBT also achieves higher
performance than T5-11B, which is a strong baseline that incorporates rich
external knowledge during pre-training stage.

2\. Better monolingual data, better results. As described in section 3.1, the
quality of monolingual data are gradually improved from “+mono30” to
“+mono100” then to “+transductive”. In most cases, it’s as expected that
“+transductive” performs better than “+mono100”, and “+mono100” performs
better than “+mono30”.

##  4 Secrets behind Iterative Back-Translation

Section 3 shows that iterative back-translation substantially improves seq2seq
models’ ability to generalize to more combinations beyond parallel data, but
it is still unclear how and why iterative back-translation succeeds (RQ 2).

To answer this research question, we first empirically analyze pseudo-parallel
data quality during the training process of iterative back-translation, and
find that errors are increasingly corrected (Section 4.1). Then, we conduct
ablation experiments to further illustrate this observation. We find that:
_even the error-prone pseudo-parallel data are beneficial._ We speculate the
reason is that knowledge of unseen combinations are implicitly injected into
the model, thereby the src2trg model and the trg2src model can boost each
other rather than harm each other (Section 4.2). Moreover, pseudo-parallel
data in iterative back-translation contain perturbations, helping models
correct errors more effectively (Section 4.3). In this section, all
experiments are conducted on the CFQ benchmark, as it is much more complex and
comprehensive than SCAN.

(a) Accuracy of Src2trg models

(b) BLEU of Trg2src models

Figure 4: Ablation experiments for understanding the key factors contribute to
the performance gain. The comparison of baseline and BT indicates that even
error-prone pseudo-parallel data are beneficial due to the injected implicit
knowledge of unseen combinations (Section 4.2). The comparison of BT and
BT+OTF indicates that perturbations brought by the on-the-fly mechanism can
prevent models learning specific incorrect bias, thus improving the
performance (Section 4.3). IBT performs best because it uses both source-side
and target-side monolingual data while others use only target-side monolingual
data.

###  4.1 Quality of Pseudo-Parallel Data

We use Figure 2 and 3 to get a better sense of the quality of pseudo-parallel
data during the training process. The x-axis represents the number of training
steps: in the first 5000 steps, we train the src2trg model and the trg2src
model with only parallel data; the iterative back-translation process starts
from step 5001 (dashed vertical lines). For each step, we use the model to
generate pseudo-parallel data from all monolingual data, and then evaluate the
generated data quality. Specifically: the src2trg model generates a SPARQL
query for each natural language utterance in the source-side monolingual data,
and we define the quality of these generated SPARQL queries (i.e., target-side
sequences) as the accuracy of them; the trg2src model generates a natural
language utterance for each SPARQL query in the target-side monolingual data,
and we define the quality of these generated natural language utterances
(i.e., source-side sequences) as the BLEU score (Papineni et al. 2002) of
them.

We observe that _iterative back-translation can increasingly correct errors in
pseudo-parallel data._ Even though the pseudo-parallel data are error-prone at
the end of initial stage (dashed horizontal lines), the accuracy/BLEU score
has increased dramatically since the iterative back-translation process
starts.

###  4.2 Impact of Error-Prone Pseudo-Parallel Data

To explore the reasons why iterative back-translation can increasingly correct
error pseudo-parallel data, we investigate whether models can benefit from the
initially generated pseudo-parallel data which are error-prone. If yes, errors
are going to be reduced during the iterative training process; otherwise,
errors are going to be reinforced.

Toward this end, we conduct two ablation experiments with “+mono30”
monolingual data setting:

  * •

BT-Src2trg: the standard back-translation method for training the src2trg
model (i.e., BT in Figure 4(a)). It consists of three phases: first, train a
src2trg model and a trg2src model using parallel data; then, generate pseudo-
parallel data from target-side monolingual data using the trg2src model;
finally, tune the src2trg model using the union of parallel data and pseudo-
parallel data.

  * •

BT-Trg2src: the standard back-translation method for training the trg2src
model (i.e., BT in Figure 4(b)). It also consists of three phrases dual to
those in BT-Src2trg.

According to the performance of BT and baseline (i.e., src2trg/trg2src models
trained only on parallel data) in Figure 4, we observe that _even error-prone
pseudo-parallel data can be beneficial._ Specifically, though the initial
pseudo-parallel data are error-prone (on average, 21.9% BLEU for Trg2src and
16.0% accuracy for Src2trg), they can still improve each other (5.4% BLEU and
4.0% accuracy gains for Trg2src and Src2trg models, respectively).

A reasonable illustration for the observation is that: even though pseudo-
parallel data are error-prone, it can still implicitly inject the knowledge of
unseen combinations into the src2trg/trg2src models, thereby boosting these
models rather than harming them.

###  4.3 Impact of Perturbations

Previous studies show that _perturbations (or noises)_ in pseudo data play an
important role in semi-supervised learning (Zhang and Zong 2016; Edunov et al.
2018; He et al. 2019; Xie et al. 2020).

In iterative back-translation, the on-the-fly mechanism (i.e., models will be
tuned each mini-batch on-the-fly with a batch of pseudo-parallel data) brings
perturbations to pseudo-parallel data. Different batches of pseudo-parallel
data are produced by different models at different steps, rather than the same
model. This makes errors more diverse, thus preventing the src2trg/trg2src
model learning specific incorrect bias from specific dual model. Therefore, it
is reasonable to speculate that some performance gains are brought by such
perturbations.

We conduct two ablation experiments (with “+mono30” monolingual data setting)
to study the impact of such perturbations:

  * •

BT-Src2trg-with-OTF: this method can be seen as iterative back-translation
without source-side monolingual data (i.e., BT+OTF in Figure 4(a)).
Specifically, during the iterative training process, the trg2src model will
only be tuned with parallel data. As Figure 3 shows, the quality of pseudo-
parallel data produced by the trg2src model would keep error-prone if it is
only tuned on parallel data (the baseline curves in Figure 3). We want to see
whether the src2trg model could be improved if the trg2src model keeps
providing error-prone pseudo-parallel data.

  * •

BT-Trg2src-with-OTF: this method can be seen as iterative back-translation
without target-side monolingual data (i.e., BT+OTF in Figure 4(b)). We want to
see whether the trg2src model could be improved if the src2trg model keeps
providing error-prone pseudo-parallel data.

According to the performance of BT and BT+OTF in Figure 4, we find that
perturbations brought by the on-the-fly mechanism do help models benefit from
error-prone pseudo-parallel data more effectively. For example, on average,
the accuracy of BT-Src2trg-with-OTF is 33.3%, while the accuracy of BT-Src2trg
is only 20.1%. According to our statistics, each sequence in target-side
monolingual data has 49.3 different back-translations during the iterative
training process. The perturbations bring 13.3% performance gain, even if the
quality of pseudo-parallel data has almost no improvement (see the baseline
curves in Figure 3).

This experimental results support our hypothesis that _perturbations brought
by the on-the-fly mechanism contributes a lot to the success of iterative
back-translation in compositional generalization benchmarks_.

##  5 Curriculum Iterative Back-Translation

As discussed in Section 4, the major reason for why iterative back-translation
succeeds is that it can increasingly correct errors in pseudo-parallel data.
Based on this observation, it is reasonable to speculate that iterative back-
translation can be further improved through injecting inductive bias that can
help errors be reduced more efficiently. Towards this end, we consider
curriculum learning (Bengio et al. 2009) as a potential solution: start out
iterative back-translation with easy monolingual data (of which the generated
pseudo-parallel data are less error-prone), then gradually increase the
difficulty of monolingual data during the training process. Based on this
intuition, we propose _Curriculum Iterative Back-Translation (CIBT)_.

Table 3: Performance (accuracy) of curriculum iterative back-translation. | IBT | CIBT with hyperparameter $c$ (steps in each stage)
---|---|---
2000 | 2500 | 3000 | 3500 | 4000
MCD1 | $64.8\pm 4.4$ | $66.1\pm 5.0$ | $66.0\pm 4.8$ | $\textbf{66.6}\pm 5.4$ | $65.9\pm 3.7$ | $65.4\pm 3.8$
MCD2 | $57.8\pm 4.9$ | $68.6\pm 2.6$ | $\textbf{69.1}\pm 3.1$ | $68.0\pm 1.9$ | $66.8\pm 2.4$ | $65.4\pm 3.1$
MCD3 | $64.6\pm 4.9$ | $70.2\pm 4.9$ | $68.4\pm 7.0$ | $\textbf{70.4}\pm 4.8$ | $69.2\pm 4.1$ | $67.0\pm 6.3$
Mean | $62.4\pm 6.1$ | $\textbf{68.3}\pm 4.1$ | $67.8\pm 4.7$ | $\textbf{68.3}\pm 4.1$ | $67.3\pm 3.4$ | $65.9\pm 4.1$

###  5.1 Method

#### Problem Formulation

We denote source-side and target-side monolingual data in iterative back-
translation as $D_{src}$ and $D_{trg}$, respectively. Suppose that we have a
simple heuristic algorithm $\mathcal{C}$, which can divide $D_{src}$ into $n$
parts (denoted as $D_{src}^{(1)}$, $D_{src}^{(2)}$, …, $D_{src}^{(n)}$), and
$D_{trg}$ can also be divided into $n$ parts (denoted as $D_{trg}^{(1)}$,
$D_{trg}^{(2)}$, …, $D_{trg}^{(n)}$). They are sorted by difficulty in
ascending order: the initial src2trg model performs roughly better on
$D_{src}^{(i)}$ than on $D_{src}^{(j)}$ if $i<j$; and the initial trg2src
model performs roughly better on $D_{trg}^{(i)}$ than on $D_{trg}^{(j)}$ if
$i<j$. We define that
$(D_{src}^{(1)},D_{trg}^{(1)}),(D_{src}^{(2)},D_{trg}^{(2)}),...,(D_{src}^{(n)},D_{trg}^{(n)})$
are $n$ curriculums from simple to difficult. Our goal is to improve the
performance of iterative back-translation with this additional curriculum
setting.

#### Method Details

Algorithm 2 details the workflow of curriculum iterative back-translation.

Algorithm 2 Curriculum Iterative Back-Translation

Input: $M_{\rightarrow}$ and $M_{\leftarrow}$, the src2trg and trg2src models
that have been initially trained on parallel data; $D_{src}$ and $D_{trg}$,
source-side and target-side monolingual data; $\mathcal{C}$, curriculum
segmentation algorithm; $c$, the number of steps each stage should be trained;
$n$, number of curriculums.

1:Use $\mathcal{C}$ to split $D_{src}$ into
$D^{(1)}_{src},D^{(2)}_{src},...,D^{(n)}_{src}$

2:Use $\mathcal{C}$ to split $D_{trg}$ into
$D^{(1)}_{trg},D^{(2)}_{trg},...,D^{(n)}_{trg}$

3:$D^{\prime}_{src}=\emptyset,D^{\prime}_{trg}=\emptyset$

4:for $t=1,2,...,n$ do $\triangleright$ $n$ stages

5: $D^{\prime}_{src}=D^{\prime}_{src}\cup D^{(t)}_{src}$

6: $D^{\prime}_{trg}=D^{\prime}_{trg}\cup D^{(t)}_{trg}$

7: Iterative back-translation ($c$ steps) to update $M_{\rightarrow}$ and
$M_{\leftarrow}$, with $D^{\prime}_{src}$ and $D^{\prime}_{trg}$ as
monolingual data

8:end for

###  5.2 Experimental Setup

We evaluate the effectiveness of curriculum iterative back-translation on the
CFQ “+mono30” setting.

#### Curriculum Segmentation.

Defining the curriculum segmentation algorithm $\mathcal{C}$ is critical in
our method. In previous research work on curriculum learning, many metrics for
curriculum segmentation have been proposed, such as length, frequency, and
perplexity.

In curriculum iterative back-translation, $\mathcal{C}$ is used to split both
$D_{src}$ and $D_{trg}$. We denote that $\mathcal{C}_{i}(s)$ is an indicator
that takes the value 1 if and only if $\mathcal{C}$ put the sample $s$ into
the $i$-th curriculum. It is a straightforward assumption that: for each
$i=1,2,...,n$, the performance of curriculum iterative back-translation would
be better if $\mathcal{C}_{i}(x)=\mathcal{C}_{i}(y)$ for any source-side
sequence $x$ paired with its ground truth target-side sequence $y$.
Intuitively, we want to ensure that $x$ and $y$ are in the same curriculum.

Based on this principle, we define $\mathcal{C}$ based on the number of
entities occurring in each source/target sample. For example, consider the
source sequence “Were M1 and M3 distributed by M0’s employer and distributed
by M2?”. It contains 4 entities (M0, M1, M2, and M3), and its corresponding
target sequence (a SPARQL query) also contains these 4 entities. Therefore, we
put them into the same curriculum. Specifically, we define 6 curriculums,
which contain monolingual data with $(\leq 1)/2/3/4/5/(\geq 6)$ entities.

Figure 5 shows that: in this entity-based curriculum setting, curriculum 1-6
are indeed arranged in order from simple to difficult. Specifically, we
evaluate the performance of the baseline model (i.e., the seq2seq model
trained on parallel data) on $D_{src}^{(1)},D_{src}^{(2)},...,D_{src}^{(6)}$,
respectively. We observe that the baseline model performs better on curriculum
1-2 than on curriculum 3-6, which indicates that this entity-based curriculum
setting is reasonable.

#### Hyperparameters

We evaluate the performance of curriculum iterative back-translation with
varying $c$ (the number of steps each stage should be trained):
2000/2500/3000/3500/4000. To be fair, after $n\times c$ steps, we continue to
train on complete monolingual data (i.e., $D_{src}$ and $D_{trg}$) for
$(25,000-n\times c)$ steps, thus keeping the number of overall training steps
the same.

###  5.3 Results and Analysis

#### Curriculum learning benefits iterative back-translation.

Figure 5: Performance of baseline model in each curriculum. Figure 6:
Performance on different subsets. This figure indicates that curriculum
learning is more beneficial to difficult data (larger $k$) than simple data
(smaller $k$).

Table 3 shows the main results. CIBT consistently outperforms IBT in all three
data splits (MCD1/MCD2/MCD3) and all hyperparameter settings ($c$
=$2000/2500/3000/3500/4000$). For MCD1/MCD2/MCD3 tasks of CFQ, CIBT
outperforms IBT by 1.8%/11.3%/5.8% accuracy scores. An interesting observation
is that incorporating curriculum learning into iterative back-translation
brings more stable performance: IBT performs much worse on MCD2 (57.8%) than
on MCD1/MCD3 (64.8%/64.6%), while CIBT’s improvement on MCD2 (11.3%) is much
better than on MCD1/MCD3 (1.8%/5.8%), making the performances on
MCD1/MCD2/MCD3 comparable (66.6%/69.1%/70.4%).

#### Curriculum learning is more beneficial to difficult data than simple
data.

Figure 6 further illustrates how curriculum learning improves the performance.
We use $k$ to denote test cases that would be put into the first $k$
curriculums, then obtain 6 subsets of test data: $T_{1}$, $T_{2}$, …, $T_{6}$.
We have $T_{1}\subset T_{2}\subset...\subset T_{6}$. As we can observe in
Figure 6, on the simplest subset ($T_{1}$), the performances of IBT and CIBT
are very close. If we consider $T_{2}$, a subset which is a bit more difficult
than $T_{1}$, CIBT performs slightly better than IBT. Similarly, we observe
that: more difficult a subset of test data is, more gains CIBT brings.
Therefore, we can conclude that curriculum learning is more beneficial to
difficult data than simple data.

##  6 Related Work

###  6.1 Compositional Generalization

Recently, exploring compositional generalization of DNN models has attracted a
large attention on different topics, e.g., visual-question answering (Hudson
and Manning 2018), algebraic compositionality (Veldhoen et al. 2016; Saxton et
al. 2019), and logic inference (Bowman, Manning, and Potts 2015; Mul and
Zuidema 2019). In this work, we focus on compositional generalization in
language, which is benchmarked by SCAN (Lake and Baroni 2018) and CFQ (Keysers
et al. 2020) tasks.

While mainstream DNN models are proved to exhibit limited compositional
generalization ability in language (Lake and Baroni 2018; Hupkes et al. 2020;
Keysers et al. 2020; Furrer et al. 2020), there have been many efforts to
address this limitation, including design specialized architectures (Russin et
al. 2019; Li et al. 2019; Gordon et al. 2019; Guo et al. 2020; Liu et al.
2020), data augmentation (Jia and Liang 2016; Andreas 2020), meta-learning
(Lake 2019; Nye et al. 2020) and pre-training models (Furrer et al. 2020).
Comparing to these previous work, this paper incorporates semi-supervised
learning into compositional generalization, which is task-agnostic and model-
agnostic, thus improving the performance on both SCAN and CFQ benchmarks.

###  6.2 Iterative Back-translation

The idea of iterative back-translation dates back at least to _back-
translation_ , which simply augments parallel training data using pseudo-
parallel data generated from only target-side monolingual data. Back-
translation has been proven effective in statistical machine translation
(Goutte et al. 2009; Bojar and Tamchyna 2011) and neural machine translation
(Sennrich, Haddow, and Birch 2016; Edunov et al. 2018; Imamura, Fujita, and
Sumita 2018; Xia et al. 2019; Wang et al. 2019). Iterative back-translation
(Hoang et al. 2018; Cotterell and Kreutzer 2018; Lample et al. 2018; Conneau
and Lample 2019) is an extension of back-translation, in which forward and
backward direction models generate pseudo-parallel data for each other and
improve each other, bringing stronger empirical performance.

To our best knowledge, this paper is the first to study iterative back-
translation from the perspective of compositional generalization. We
demonstrate that iterative back-translation can help seq2seq models make
better generalizations to much more combinations, thus broadening the
understanding of iterative back-translation.

##  7 Conclusion

In this paper, we revisit iterative back-translation from the perspective of
compositional generalization. We find that iterative back-translation is an
effective method that exploits a large amount of monolingual data to enable
seq2seq models better generalize to more combinations beyond limited parallel
data. We also find that iterative back-translation has the ability to
increasingly correct errors in pseudo-parallel data, thus contributing to its
success. To encourage this behaviour, we propose curriculum iterative back-
translation, which explicitly improves the quality of pseudo-parallel data,
thus further improving the performance.

## References

  * Andreas (2020) Andreas, J. 2020.  Good-Enough Compositional Data Augmentation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 7556–7566. Association for Computational Linguistics.  doi:10.18653/v1/2020.acl-main.676.  URL https://www.aclweb.org/anthology/2020.acl-main.676.
  * Artetxe et al. (2018) Artetxe, M.; Labaka, G.; Agirre, E.; and Cho, K. 2018.  Unsupervised neural machine translation.  In _Proceedings of the Sixth International Conference on Learning Representations_.
  * Bengio (2019) Bengio, Y. 2019.  Towards Compositional Understanding of the World by Agent-Based Deep Learning.  _NeurIPS’2019 Workshop on Context and Compositionality in Biological and Artificial Neural Networks_ .
  * Bengio et al. (2009) Bengio, Y.; Louradour, J.; Collobert, R.; and Weston, J. 2009.  Curriculum learning.  In _Proceedings of the 26th annual international conference on machine learning_ , 41–48.
  * Bojar and Tamchyna (2011) Bojar, O.; and Tamchyna, A. 2011.  Improving translation model by monolingual data.  In _Proceedings of the Sixth Workshop on Statistical Machine Translation_ , 330–336.
  * Bowman, Manning, and Potts (2015) Bowman, S. R.; Manning, C. D.; and Potts, C. 2015.  Tree-structured composition in neural networks without tree-structured architectures.  In _Proceedings of the 2015th International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches-Volume 1583_ , 37–42. CEUR-WS. org.
  * Cao et al. (2019) Cao, R.; Zhu, S.; Liu, C.; Li, J.; and Yu, K. 2019.  Semantic Parsing with Dual Learning.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , 51–64.
  * Chapelle, Scholkopf, and Zien (2009) Chapelle, O.; Scholkopf, B.; and Zien, A. 2009.  Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews].  _IEEE Transactions on Neural Networks_ 20(3): 542–542.
  * Chomsky (1965) Chomsky, N. 1965.  _Aspects of the Theory of Syntax_ , volume 11.  MIT press.
  * Conneau and Lample (2019) Conneau, A.; and Lample, G. 2019.  Cross-lingual language model pretraining.  In _Advances in Neural Information Processing Systems_ , 7059–7069.
  * Cotterell and Kreutzer (2018) Cotterell, R.; and Kreutzer, J. 2018.  Explaining and generalizing back-translation through wake-sleep.  _arXiv preprint arXiv:1806.04402_ .
  * Edunov et al. (2018) Edunov, S.; Ott, M.; Auli, M.; and Grangier, D. 2018.  Understanding Back-Translation at Scale.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , 489–500.
  * Fodor and Pylyshyn (1988) Fodor, J. A.; and Pylyshyn, Z. W. 1988.  Connectionism and cognitive architecture: A critical analysis.  _Cognition_ 28(1-2): 3–71.
  * Furrer et al. (2020) Furrer, D.; van Zee, M.; Scales, N.; and Schärli, N. 2020.  Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures.  _arXiv preprint arXiv:2007.08970_ .
  * Gordon et al. (2019) Gordon, J.; Lopez-Paz, D.; Baroni, M.; and Bouchacourt, D. 2019.  Permutation equivariant models for compositional generalization in language.  In _International Conference on Learning Representations_.
  * Goutte et al. (2009) Goutte, C.; Cancedda, N.; Dymetman, M.; and Foster, G. 2009.  _Learning machine translation_.  Massachusetts Institute of Technology.
  * Guo et al. (2020) Guo, Y.; Lin, Z.; Lou, J.-G.; and Zhang, D. 2020.  Hierarchical Poset Decoding for Compositional Generalization in Language.  _Advances in Neural Information Processing Systems_ 33\.
  * He et al. (2016) He, D.; Xia, Y.; Qin, T.; Wang, L.; Yu, N.; Liu, T.-Y.; and Ma, W.-Y. 2016.  Dual learning for machine translation.  In _Advances in neural information processing systems_ , 820–828.
  * He et al. (2019) He, J.; Gu, J.; Shen, J.; and Ranzato, M. 2019.  Revisiting Self-Training for Neural Sequence Generation.  In _International Conference on Learning Representations_.
  * Hoang et al. (2018) Hoang, V. C. D.; Koehn, P.; Haffari, G.; and Cohn, T. 2018.  Iterative back-translation for neural machine translation.  In _Proceedings of the 2nd Workshop on Neural Machine Translation and Generation_ , 18–24.
  * Hudson and Manning (2018) Hudson, D. A.; and Manning, C. D. 2018.  Compositional Attention Networks for Machine Reasoning.  In _International Conference on Learning Representations_.
  * Hupkes et al. (2020) Hupkes, D.; Dankers, V.; Mul, M.; and Bruni, E. 2020.  Compositionality Decomposed: How do Neural Networks Generalise?  _Journal of Artificial Intelligence Research_ 67: 757–795.
  * Imamura, Fujita, and Sumita (2018) Imamura, K.; Fujita, A.; and Sumita, E. 2018.  Enhancement of encoder and attention using target monolingual corpora in neural machine translation.  In _Proceedings of the 2nd Workshop on Neural Machine Translation and Generation_ , 55–63.
  * Jia and Liang (2016) Jia, R.; and Liang, P. 2016.  Data Recombination for Neural Semantic Parsing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 12–22. Berlin, Germany: Association for Computational Linguistics.  doi:10.18653/v1/P16-1002.  URL https://www.aclweb.org/anthology/P16-1002.
  * Keysers et al. (2020) Keysers, D.; Schärli, N.; Scales, N.; Buisman, H.; Furrer, D.; Kashubin, S.; Momchev, N.; Sinopalnikov, D.; Stafiniak, L.; Tihon, T.; Tsarkov, D.; Wang, X.; van Zee, M.; and Bousquet, O. 2020.  Measuring Compositional Generalization: A Comprehensive Method on Realistic Data.  In _International Conference on Learning Representations_.  URL https://openreview.net/forum?id=SygcCnNKwr.
  * Lake and Baroni (2018) Lake, B.; and Baroni, M. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _International Conference on Machine Learning_ , 2873–2882.
  * Lake (2019) Lake, B. M. 2019.  Compositional generalization through meta sequence-to-sequence learning.  In _Advances in Neural Information Processing Systems_ , 9791–9801.
  * Lake et al. (2017) Lake, B. M.; Ullman, T. D.; Tenenbaum, J. B.; and Gershman, S. J. 2017.  Building machines that learn and think like people.  _Behavioral and Brain Sciences_ 40\.
  * Lample et al. (2018) Lample, G.; Conneau, A.; Denoyer, L.; and Ranzato, M. 2018.  Unsupervised Machine Translation Using Monolingual Corpora Only.  In _International Conference on Learning Representations_.
  * Li et al. (2019) Li, Y.; Zhao, L.; Wang, J.; and Hestness, J. 2019.  Compositional Generalization for Primitive Substitutions.  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)_ , 4284–4293.
  * Liu et al. (2020) Liu, Q.; An, S.; Lou, J.-G.; Chen, B.; Lin, Z.; Gao, Y.; Zhou, B.; Zheng, N.; and Zhang, D. 2020.  Compositional Generalization by Learning Analytical Expressions.  _Advances in Neural Information Processing Systems_ 33\.
  * Mikolov, Joulin, and Baroni (2016) Mikolov, T.; Joulin, A.; and Baroni, M. 2016.  A roadmap towards machine intelligence.  In _International Conference on Intelligent Text Processing and Computational Linguistics_ , 29–61. Springer.
  * Mollica et al. (2020) Mollica, F.; Siegelman, M.; Diachek, E.; Piantadosi, S. T.; Mineroff, Z.; Futrell, R.; Kean, H.; Qian, P.; and Fedorenko, E. 2020.  Composition is the core driver of the language-selective network.  _Neurobiology of Language_ 1(1): 104–134.
  * Montague (1974) Montague, R. 1974.  Formal philosophy, ed. r. thomason.  _New Haven_ .
  * Mul and Zuidema (2019) Mul, M.; and Zuidema, W. 2019.  Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization.  _arXiv preprint arXiv:1906.00180_ .
  * Nye et al. (2020) Nye, M. I.; Solar-Lezama, A.; Tenenbaum, J. B.; and Lake, B. M. 2020.  Learning Compositional Rules via Neural Program Synthesis.  _arXiv preprint arXiv:2003.05562_ .
  * Papineni et al. (2002) Papineni, K.; Roukos, S.; Ward, T.; and Zhu, W.-J. 2002.  BLEU: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , 311–318.
  * Partee (1984) Partee, B. 1984.  Compositionality. Varieties of formal semantics: Proceedings of the fourth Amsterdam colloquium, ed. by Frank Veltman, 281–311.
  * Russin et al. (2019) Russin, J.; Jo, J.; O’Reilly, R. C.; and Bengio, Y. 2019.  Compositional generalization in a deep seq2seq model by separating syntax and semantics.  _arXiv preprint arXiv:1904.09708_ .
  * Saxton et al. (2019) Saxton, D.; Grefenstette, E.; Hill, F.; and Kohli, P. 2019.  Analysing Mathematical Reasoning Abilities of Neural Models.  In _International Conference on Learning Representations_.
  * Sennrich, Haddow, and Birch (2016) Sennrich, R.; Haddow, B.; and Birch, A. 2016.  Improving Neural Machine Translation Models with Monolingual Data.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 86–96.
  * Skorokhodov et al. (2018) Skorokhodov, I.; Rykachevskiy, A.; Emelyanenko, D.; Slotin, S.; and Ponkratov, A. 2018.  Semi-supervised neural machine translation with language models.  In _Proceedings of the AMTA 2018 Workshop on Technologies for MT of Low Resource Languages (LoResMT 2018)_ , 37–44.
  * Veldhoen et al. (2016) Veldhoen, S.; Hupkes, D.; Zuidema, W. H.; et al. 2016.  Diagnostic Classifiers Revealing how Neural Networks Process Hierarchical Structure.  In _CoCo@ NIPS_ , 69–77.
  * Wang et al. (2019) Wang, S.; Liu, Y.; Wang, C.; Luan, H.; and Sun, M. 2019.  Improving Back-Translation with Uncertainty-based Confidence Estimation.  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)_ , 791–802.
  * Xia et al. (2019) Xia, M.; Kong, X.; Anastasopoulos, A.; and Neubig, G. 2019.  Generalized Data Augmentation for Low-Resource Translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , 5786–5796.
  * Xie et al. (2020) Xie, Q.; Luong, M.-T.; Hovy, E.; and Le, Q. V. 2020.  Self-training with noisy student improves imagenet classification.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 10687–10698.
  * Yin et al. (2018) Yin, P.; Zhou, C.; He, J.; and Neubig, G. 2018.  StructVAE: Tree-structured Latent Variable Models for Semi-supervised Semantic Parsing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 754–765.
  * Zhang and Zong (2016) Zhang, J.; and Zong, C. 2016.  Exploiting source-side monolingual data in neural machine translation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , 1535–1545.


# A New Fixed Point Theorem for Non-expansive Mappings and Its Application

Chunyan Yang
Department of Mathematics, Sichuan University, Chengdu 610064,P.R.China
e-mail<EMAIL_ADDRESS>
(Feb,12,2012)

Abstract. We use $KKM$ theorem to prove the existence of a new fixed point
theorem for non-expansive mapping:Let M be a bounded closed convex subset of
Hilbert space H, and $A:M\rightarrow M$ be a non-expansive mapping, then
exists a fixed point of A in M, we also apply this Theorem to study the
solution for an integral equation,we can weak some conditions comparing with
Banach’s contraction mapping principle.

Key words: Bounded closed convex subset, non-expansive mapping, fixed
point,integral equation

2000 AMS Subject Classification: 47H10,47J25,47J05

##  1 Introduction and Main Results

###

It is well-known that $Banach$, $Schauder$,$Brouwer$ presented three kinds of
fixed point theorems in 1910’s-1930’s. $Banach^{\prime}s$ fixed point theorem
is also called contraction mapping principle , and $Schauder^{\prime}s$ fixed
point theorem is a generalization of $Brouwer^{\prime}s$ from finite dimension
into infinite dimension. Specifically, for a compact operator A, if its domain
is a bounded non-empty closed convex subset, then there is at least one fixed
point u : $A\cdot u=u$. All the above three fixed point theorems need good
operators, for example, the compactness for the operator can make the unit
closed sphere in infinite dimensional space be a compact set.

###

Here, a nature question is whether the fixed point theorem of other good
operator or mapping could be established.

###

A problem is whether there is a fixed point theorem for A when $k=1$ (where A
is called the non-expansive mapping). For solving this problem, the main tool
we will use is $KKM$ theorem.It’s well known that the Polish mathematician
$Knaster$, $Kuratowski$, $Mazurkiewicz$ got $KKM$ theorem in 1929, they also
applied it to the proof of $Brouwer$ fixed point theorem.

###

Theorem1.1.( Banach fixed point theorem([1])): Let $(X,d)$ be a complete
metric space, and $A:X\rightarrow X$ be a contraction mapping, that is , for
any x,y $\in$ X, there holds $d(Ax,Ay)\leq kd(x,y),(0\leq k<1)$. Then there is
a unique fixed point $x*$ for $A$, i.e. $Ax*=x*$.
Banach’s fixed point theorem can be applied to many fields in
mathematics,especially to integral equation:

$u(x)=\lambda\int_{a}^{b}F(x,y,u(y))dy+f(x),\ \ \ \ \ a\leq x\leq b$ $None$

###

Theorem1.2.([2]) Assume

(a) $f:[a,b]\rightarrow R$ is continuous

(b) $F(x,y,u(y))=K(x,y)u(y)$,and $K:[a,b]\times[a,b]\rightarrow R$ is
continuous.

Let $\Gamma=\max_{a\leq x,y\leq b}|K(x,y)|$,and

(c) real number $\lambda$ be given such that
$(b-a)\cdot|\lambda|\cdot\Gamma<1$.

Then the problem (1.1) has a unique solution $u\in X=C[a,b]$.
In this paper,we get:

###

Theorem1.3. Let M be a bounded closed convex subset of Hilbert space H, and
$A:M\rightarrow M$ be a non-expansive mapping, then exists a fixed point of A
in M.

###

Notice that our fixed point theorem is in Hilbert Space , since any linear
continuous functional in Hilbert space can be represented by the inner
product, which is called $Riesz$ representation theorem, while in the Banach
space no such theorem.

We apply the above theorem to linear integral equation,we obtain

###

Theorem1.4. For the integral equation(1.1) with $F(x,y,u(y))=K(x,y)u(y),$
assume

(1)The function $f:[a,b]\rightarrow R$ is in $L^{2}[a,b].$

(2)$K(x,y)\in L^{2}([a,b]\times[a,b])$,$K(x,\cdot)\in L^{2}[a,b]$,for any
given $x\in[a,b]$

(3)Let the real number $\lambda$ be given such that,
$|\lambda|\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy\leq 1,iff\equiv 0;$ and,

$|\lambda|\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy<1,iff\neq 0.$

Then (1.1) has at least one solution $u\in L^{2}[a,b].$

##  2 Related Definitions and Well-known Theorems

###

Definition 2.1. ($KKM$ mapping([3])): The mapping $G:X\rightarrow 2^{R^{n}}$ ,
where $X$ is a non-empty subset of the vector space $R^{n}$ , is called $KMM$
mapping. if $\forall\\{x_{0},\ldots,x_{n}\\}\subset X$, we have
$Co(\\{x_{0},\ldots,x_{n}\\})\subset\cup^{n}_{i=1}G(x_{i})$, where
$Co(\\{x_{0},\ldots,x_{n}\\})$ is the closed convex hull of
$x_{0},\ldots,x_{n}.$

###

Theorem 2.1. ($KKM$ Theorem ([4])) Let $\Delta_{n}$ be n dimensional simplex
which has vertices $\\{e_{0},\ldots,e_{n}\\}$ and is in $R^{n+1}$. Let
$M_{0},\ldots,M_{n}$ be n dimensional closed subsets in $R^{n+1}$, which
satisfy $\forall\\{e_{i0},\ldots,e_{ik}\\}\subset\\{e_{0},\ldots,e_{n}\\}$,
$Co(\\{e_{i0},\ldots,e_{ik}\\})\subset\cup_{j=0}^{k}M_{ij}$. Then $\cap M_{i}$
is not empty.

###

Theorem 2.2. ($FKKM$ ([5])): Let $F^{n}$ be Hausdorff linear topological
space, X be a non-empty subset of $F^{n}$. Let $G:X\longrightarrow 2^{F^{n}}$
be a $KKM$ mapping, and $G(x)$ is weakly compact for any $x\in X$ . Then
$\cap_{x\in X}G(x)$ is non-empty.

###

Definition 2.2.( Semi-continuous([6])): Let $X$ be a Banach space, $X^{*}$ be
its dual space. Let $T:X\rightarrow X^{*}$. If $\forall y\in X$, $\forall
t_{n}\geq 0$and $x_{0}+t_{n}\cdot y\in X$, we have $lim_{x_{0}+t_{n}\cdot
y\rightarrow x_{0}}T(x_{0}+t_{n}\cdot y)\rightarrow T(x_{0})$, we call T is
$semi-continuous$ at point $x_{0}$. Furthermore if T is $semi-continuous$ at
every point x in X, T is called $semi-continuous$ on X.

###

Definition 2.3.( Monotonicity([7])): Let X be a Banach space, $X^{*}$ be its
dual space. We call $T:\rightarrow 2^{X^{*}}$ monotonous , if $<u-v,x-y>\geq
0$ ,for $\forall x,y\in X$, $u\in T(x),v\in T(y)$.

##  3 Some Lemmas for the Proof of Our Theorem 1.3.

###

We require the following Lemmas for proving the fixed point theorem of the
non-expansive mapping using the $KKM$ theorem .

###

Lemma 3.1: Let M be a bounded closed convex subset of Hilbert space H,
$L:M\rightarrow H$ be monotonous semi-continuous mapping. If $x_{0}\in M$,
then

$<L(x_{0}),y-x_{0}>\geq 0,\forall y\in M,$

if and only if

$<L(y),y-x_{0}>\geq 0,\forall y\in M.$

Proof Let $x_{0}\in M$ such that : $<L(x_{0}),y-x_{0}>\geq 0,\forall y\in M$.
Since the monotonicity of L, we have

$<L(y)-L(x_{0}),y-x_{0}>\geq
0\Leftrightarrow<L(y),y-x_{0}>-<L(x_{0}),y-x_{0}>\geq 0,\forall y\in M.$

Thus ,

$<L(y),y-x_{0}>\geq<L(x_{0}),y-x_{0}>\geq 0,\forall y\in M.$

On the other hand,if $x_{0}\in M$ then

$<L(y),y-x_{0}>\geq 0,\forall y\in M.$

We let

$y=h\cdot\mu+(1-h)x_{0},\forall h\in(0,1],\forall\mu\in M,$

since M is convex, then $y\in M$. Thus,

$<L(y),y-x_{0}>=<L(x_{0}+h\cdot(\mu-x_{0})),h\cdot(\mu-x_{0})>\geq 0(h>0).$

We let $h\rightarrow 0$, then $x_{0}+h\cdot(\mu-x_{0})\rightarrow x_{0}$,
since L is semi-continuous , so

$<L(x_{0}),(\mu-x_{0})>\geq 0,\forall\mu\in M.$

###

Lemma 3.2([8]): Let M be a bounded closed convex subset of Hilbert space H,
and$L:M\rightarrow H,P:M\rightarrow 2^{M}$, and $P(y)=\\{x\in M,<L(x),x-y>\leq
0\\},\forall y\in M$, then P is a $KKM$ mapping.
Proof: If P is not a $KKM$ mapping. By the definition of $KKM$ mapping,
$\exists\\{x_{0}\ldots x_{n}\\}=w$, $w\subset M$, let $\bar{x}=\sum h_{i}\cdot
x_{i}\in Co(w),(\sum h_{i}=1,h_{i}\geq 0)$, then
$\bar{x}\not\in\cup_{i=0}^{n}P(x_{i})$, that is to say,
$<L(\bar{x}),\bar{x}-y>>0$. As the arbitrariness of $y$, let $y=\sum
h_{i}\cdot x_{i}$, we have$<L(\bar{x}),\bar{x}-x_{i}>>0$, then
$<L(\bar{x}),h_{i}\cdot(\bar{x}-x_{i})>>0(\exists h_{i}>0)$, thus,

$<L(\bar{x}),\sum h_{i}\cdot(\bar{x}-x_{i})>=<L(\bar{x}),\sum
h_{i}\cdot\bar{x}-\sum h_{i}\cdot x_{i}>=<L(\bar{x}),\bar{x}-y>=0.$

This is a contradiction with $<L(\bar{x}),\bar{x}-y>>0,\forall y\in M$. Hence
P is a $KKM$ mapping.

###

Lemma 3.3: Let M be a bounded closed convex subset of Hilbert space H,
$L:M\rightarrow H$ be a semi-continuous monotonous mapping, then $\exists
x_{0}\in M$ s.t.

$<L(x_{0}),x_{0}-y>\leq 0,\forall y\in M$

Proof: Let $P:M\rightarrow 2^{M}$ and $P(y)=\\{x\in M,<L(x),x-y>\leq
0\\},\forall y\in M$. According to Lemma 3.2,P is a $KKM$ mapping. Mean-while,
let mapping$J:M\rightarrow 2^{M}$ and

$J(y)=\\{x\in M,<L(y),x-y>\leq 0\\},\forall y\in M.$

By the monotonicity of the operator L and Lemma 3.1,

$P(y)\subset J(y),\forall y\in M.$

Since P is a $KKM$ mapping, $Co(\\{x_{0}\ldots
x_{n}\\})\subset\cup_{i=0}^{n}P(x_{i})\subset\cup_{i=0}^{n}J(x_{i})$. hence J
is $KKM$ mapping.

Furthermore, it can be easy to prove that $J(y)$ is weakly compact. In fact,
Since M is a bounded closed convex subset, it can be convinced that M is
weakly compact. But $J(y)\subset M$, thus we only need to prove $J(y)$ is
weakly closed. In order to do that let $y_{n}\in J(y)\subset M$, s.t.

$y_{n}\rightharpoonup y_{0},so,y_{n}-y\rightharpoonup y_{0}-y,\forall y\in M.$

According to the semi-continuity of
L,$<L(y),y_{n}-y>\rightarrow<L(y),y_{0}-y>$. By $y_{n}\in J(y)$,we have
$<L(y),y_{n}-y>\leq 0$, so $<L(y),y_{0}-y>\leq 0$. Hence $y_{0}\in J(y)$, that
is to say, $J(y)$ is weakly closed.

From the above proof, J is a $KKM$ mapping, and $\forall y,J(y)$ is weakly
compact. According to $FKKM$ theorem, $\cap_{y\in M}J(y)\neq\varnothing$.
According to Lemma 3.1,$\cap_{y\in M}J(y)=\cap_{y\in
M}P(y)\neq\varnothing$,thus

$\exists x_{0}\in\cap_{y\in M}P(y),s.t.,\\\ <L(x_{0}),x_{0}-y>\leq 0,\forall
y\in M.$

##  4 The Proof of Fixed Point Theorem1.3 for the Non-Expansive Mapping

###

Proof: Let $L(x)=x-A(x),\forall x\in M$, then $L:M\rightarrow H$.By the non-
expansive property for the operator A ,we will prove L= I - A is a monotonous
operator:

$<L(x)-L(y),x-y>\geqslant 0,\forall x,y\in M.$

In fact,

$\displaystyle<L(x)-L(y),x-y>$ $\displaystyle=$ $\displaystyle<x-y-(Ax-
Ay),x-y>$ $\displaystyle=$ $\displaystyle\|x-y\|^{2}-<Ax-Ay,x-y>$
$\displaystyle\geq$ $\displaystyle\|x-y\|^{2}-\|Ax-Ay\|^{2}\cdot\|x-y\|^{2}$
$\displaystyle\geq$ $\displaystyle\|x-y\|^{2}-\|x-y\|^{2}=0.$

Since A is non-expansive mapping :$\forall x,y\in M$ ,$\|Ax-
Ay\|\leq\|x-y\|$,it can be derived that L is semi-continuous mapping.
According to Lemma 3.3, $\exists x_{0}\in M$ ,s.t.

$<L(x_{0}),x_{0}-x>\leq 0,\forall x\in M$ $None$

Specially we let $x=A(x_{0})\in M$ and substitute it into (4.1) ,we get:

$<L(x_{0}),x_{0}-A(x_{0})>\leq 0$ $None$

Since $L(x_{0})=x_{0}-A(x_{0})$, so from (4.2) we have $\|x_{0}-A(x_{0})\|\leq
0$. It’s clearly that norm $\|x_{0}-A(x_{0})\|\geq 0$, hence
$\|x_{0}-A(x_{0})\|=0$, that is to say, $A(x_{0})=x_{0}.$

##  5 The Proof of Theorem1.4

###

Proof: Let $(Au)(x)=\lambda\int_{a}^{b}F(x,y,u(y))dy+f(x)$,

$\displaystyle\|Au-Av\|^{2}$ $\displaystyle=$
$\displaystyle\int_{a}^{b}|\lambda\int_{a}^{b}K(x,y)((u(y)-v(y))dy|^{2}dx$
$\displaystyle\leq$
$\displaystyle\lambda^{2}\int_{a}^{b}[\int_{a}^{b}|K|^{2}dy\int_{a}^{b}|u(y)-v(y)|^{2}dy]dx$
$\displaystyle=$
$\displaystyle[\lambda^{2}\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]\cdot\|u-v\|_{L^{2}}^{2}.$

If $[\lambda^{2}\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]\leq 1$, then A is
non-expansive mapping.

Furthermore,we restrict A on a bounded closed convex subset M of $L^{2}$ such
that $AM\subseteq M$.Given $r>o$,let$M=\\{u\in L^{2}|\|u\|_{L^{2}}\leq r\\}$,

$\displaystyle\|Au(x)\|_{L^{2}}$ $\displaystyle\leq$
$\displaystyle\|\lambda\int_{a}^{b}F(x,y,u(y))dy\|_{L^{2}}+\|f\|_{L^{2}}$
$\displaystyle\leq$
$\displaystyle|\lambda|[\int_{a}^{b}|\int_{a}^{b}Fdy|^{2}dx]^{1/2}+\|f\|_{L^{2}}$
$\displaystyle\leq$
$\displaystyle|\lambda|\\{\int_{a}^{b}[\int_{a}^{b}|K(x,y)u(y)|dy]^{2}dx\\}^{1/2}+\|f\|_{L^{2}}$
$\displaystyle\leq$
$\displaystyle|\lambda|\\{\int_{a}^{b}[\int_{a}^{b}|K|^{2}dy\int_{a}^{b}|u(y)|^{2}dy]dx\\}^{1/2}$
$\displaystyle=$
$\displaystyle|\lambda|[\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]^{1/2}\cdot\|u\|_{L^{2}}+\|f\|_{L^{2}}$
$\displaystyle\leq$
$\displaystyle|\lambda|[\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]^{1/2}\cdot
r+\|f\|_{L^{2}}$ $\displaystyle\leq$ $\displaystyle r.$

(1).If $f\equiv 0$,and

$|\lambda|[\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]^{1/2}\leq 1.$

Then we can choose any given $r>0$.

(2).If $f\neq 0$,and

$|\lambda|[\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]^{1/2}<1.$

Then choose r such that,

$r\geq\frac{\|f\|_{L^{2}}}{1-|\lambda|[\int_{a}^{b}\int_{a}^{b}|K(x,y)|^{2}dxdy]^{1/2}}.$

Acknowledgements. I would like to thank Professor Zhang Shiqing for his
lectures on Functional Analysis ,the paper was written when I attended his
lectures, I would like to thank Professor Shiqing Zhang for his many helpful
discussions,encouragements and suggestions and corrections,this paper is
supported partially by NSF of China.

## References

  * [1] E.Zeidler,Applied functional analysis:main principles and their applications ,Springer,1995.
  * [2] E.Zeidler,Applied functional analysis:application to mathematical physics,Springer,1995,P.22-23.
  * [3] K.C.Border,Fixed point theorems with applications to ecomomics and game theory,Cambridge University Press,2009,P.26.
  * [4] B.Knaster,C.Kuratowski and S.Muzurkiewicz.,Ein Beweis des Fixepunktsatzes fur n-dimensional simplexe,Fund.Math.14(1929),P.132-137.
  * [5] K.Fan,A generalization of Tychonoff’s fixed point theorm ,Ann.Math.142(1961),P.303-310.
  * [6] W.Hang, X.Cheng,An introduction to variational inequalities :elementary theory,numerical analysis and applications,Academic Press,2003,P.92.
  * [7] B.Meng, X.Cao,A course in opreater and game theory,The MIT Press,1998,P.36.
  * [8] S.Itoh,W.Takahashi,K.Yanagi,Varicational Inequalities and complementarity problems,J.Math.Soc.Japan,1978,P.17-55.