From Base to Conversational: Japanese Instruction Dataset and Tuning Large Language Models

Masahiro Suzuki

The University of Tokyo

Tokyo, Japan

Masanori Hirano

The University of Tokyo

Tokyo, Japan

Hiroki Sakaji

The University of Tokyo

Tokyo, Japan

Instruction tuning is essential for large language models (LLMs) to become interactive.
While many instruction tuning datasets exist in English, there is a noticeable lack in other languages.
Also, their effectiveness has not been well verified in non-English languages.
We construct a Japanese instruction dataset by expanding and filtering existing datasets and apply the dataset to a Japanese pre-trained base model.
We performed Low-Rank Adaptation (LoRA) tuning on both Japanese and English existing models using our instruction dataset.
We evaluated these models from both quantitative and qualitative perspectives.
As a result, the effectiveness of Japanese instruction datasets is confirmed.
The results also indicate that even with relatively small LLMs, performances in downstream tasks would be improved through instruction tuning.
Our instruction dataset, tuned models, and implementation are publicly available online.

Large Language Model (LLM), Instruction Dataset, Instruction Tuning, Japanese

§ INTRODUCTION

Large language models (LLMs) have been making remarkable progress in performance and generalization in recent years.
Various Transformer-based [1] language models, such as BERT [2], RoBERTa [3], and the GPT series [4, 5, 6], have demonstrated high performance derived from pre-training.
Furthermore, since 2022, a large number of models, such as OPT [7], GPT-NeoX-20B [8], UL2 [9], PaLM [10], BLOOM [11], Pythia [12], and LLaMA series [13, 14], have emerged as models that show higher performance by scaling their size [15].

Although there is still difficulty in few-shot or zero-shot performance on unseen tasks, instruction tuning can address this issue [16].
Instruction tuning is a training method that improves the performance in unseen tasks by solving various tasks described via natural language instructions [16].
Starting with the enhancement of performance in various tasks by GPT-3 [6] under a few-shot setting given in natural language, there has been an increasing demand for responses in formats that are closer to question-answering or conversation, especially formats that are not similar to the pre-training data.

An increasing number of datasets for instruction tuning and instruct-tuned models are being made available to the public.
For instance, various datasets like FLAN [16], P3 [17], databricks-dolly-15k [<https://huggingface.co/datasets/databricks/databricks-dolly-15k>], and OASST1 [18] have been proposed and made public.
As publicly available models, Flan-T5 [19] was constructed using FLAN and T0 was constructed using P3 respectively.
Also, Dolly [20] is a model with instruction tuning applied to Pythia [12], while Vicuna [21] and Alpaca [22] are models with instruction tuning applied to LLaMA [13].

However, these models are not fully compatible with languages other than English.
The datasets used for instruction tuning in Dolly, Alpaca, and Vicuna are only in English, making it difficult to gain the benefits of these models in languages other than English.
Many instruction datasets have been constructed in English, and there are not many efforts to construct instruction datasets in languages other than English.
While there are movements to construct instruction datasets in Chinese [23], most instruction dataset in non-English languages are built from outputs of models with licensing restrictions, such as translations of the Alpaca dataset [22] or the ShareGPT52K [<https://huggingface.co/datasets/RyokoAI/ShareGPT52K>] constructed from ChatGPT outputs.
In languages other than English, the scarcity of comprehensive instruction datasets means that the verification of instruction tuning effects is limited [24].
In Japanese, only some data from translated Alpaca [22] and OASST1 [18] exists, and there's a lack of dataset diversity, with quantitative evaluations of instruction tuning yet to be conducted.
While constructing and evaluating datasets in languages other than English is a crucial step towards building language models that can interact in various languages, it's still very much in its early stages.

To tackle the issue of the lack of Japanese instruction dataset, the study [25] gathers various Japanese datasets to build an instruction dataset.
While this dataset seems valuable, the effect of instruction tuning is only shown qualitatively and not quantitatively.
Furthermore, the majority of this dataset consists of translation tasks.
While it is considered that the translation tasks are effective when adapting English-based models to Japanese, these tasks may not be optimal for Japanese-based models.
To apply the instruction dataset to a Japanese-based model, it is desirable to filter out the translation data and construct an instruction dataset consisting solely of Japanese.

We construct an instruction dataset consisting solely of Japanese for instruction tuning based on a Japanese model by filtering and expanding the Japanese instruction dataset [25].
The constructed dataset contains about 2.5 million samples and 5 tasks, such as commonsense, summarization, reading comprehension, simplification, and correction.
Using this dataset, which contains various tasks, we perform instruction tuning on both Japanese-based and English-based LLMs.
For Japanese-based models, we conduct tuning using an instruction dataset without translation data, while for English-based models, we do using an instruction dataset that includes translation data.
As a result of quantitative evaluation with the tuned model, we demonstrate that instruction tuning in Japanese improve the performance in downstream tasks, thereby illustrating the effectiveness of the Japanese instruction dataset.
The following materials used in this study are available as open source.

* Japanese instruction dataset:

* Tuned model (Stormy 10 epochs):

* Tuned model (LLaMA 7B 5 epochs):

* Implementation for training and evaluation:

Here are our main contributions: (1) We construct a Japanese instruction dataset, llm-japanese-dataset-vanilla, for Japanese-based models; (2) We clarified the benefits of instruction tuning for Japanese and English models from evaluating with some Japanese downstream tasks; (3) Unlike previous research [16], we show that even with smaller model sizes, instruction tuning can lead to performance gains in downstream tasks.

Datasets and task clusters used in llm-japanese-dataset-vanilla v1.0.1.

§ INSTRUCTION DATASET

We construct a Japanese instruction dataset without translation tasks.
We use the llm-japanese-dataset v0.1.0 [25] as a main data source for the Japanese instruction dataset and expand this dataset with additional Japanese datasets.
The llm-japanese-dataset v0.1.0 contains about 8.4 million instruction examples, of which more than 75 % (6,581,044) are constructed based on translation data.
This dataset is intended to link English and Japanese and extract the knowledge learned in English for use in Japanese as well, considering that many LLMs like LLaMA show good performance in English.
However, when it comes to Japanese-based models, they are usually pre-trained with Japanese corpora.
The need for the English part of this dataset is relatively low because the part aimed to link English and Japanese.
Therefore, we extract 1,811,964 data excluding translation tasks from the llm-japanese-dataset v0.1.0.
Furthermore, to expand the variety of datasets, we incorporated the Japanese Wikipedia Typo Dataset (Wikipedia Typo) [26] and the Japanese Question-Answering Corpus (JQAC) [27].
From the Wikipedia Typo and JQAC, we newly created 697,316 and 906 instruction entries respectively.
Additionally, we addressed licensing issues present in version v0.1.0, and ultimately constructed a total of 2,463,624 instruction data entries, releasing it as llm-japanese-dataset-vanilla v1.0.1 [<https://huggingface.co/datasets/izumi-lab/llm-japanese-dataset-vanilla>].
Figure <ref> shows datasets and task classifications included in llm-japanese-dataset-vanilla v1.0.1.

We use the instruction, input, and response included in llm-japanese-dataset-vanilla v0.1.0, following the format below.

Originally written in Japanese.

Prompt format with input
9.5pt13ptBelow is an instruction that describes a task, paired with an input that provides further context. Write a response that appropriately completes the request.

### Instruction:

### Input:

### Response:

Prompt format with no input
9.5pt13ptBelow is an instruction that describes a task. Write a response that appropriately completes the request.

### Instruction:

### Response:

The parameters of LoRA tuning

Parameter     Stormy     Instruct LLaMA 7B     Instruct LLaMA 13B[25]
Base Model     CALM 7B     LLaMA 7B     LLaMA 13B

Learning Rate     3e-4     3e-4     3e-4

Sequence Length     300     256     256

Batch     128     128     130

# of data     1.4M     8.4M     8.4M

Epochs     10     5     1

$r$ in LoRA     4     4     4

$\alpha$ in LoRA     16     16     16

Dropout Ratio of LoRA     0.05     0.05     0.05

Tuning Parameters     query_key_value     q_proj, v_proj     q_proj, v_proj

§ INSTRUCTION LORA TUNING

We perform Low-Rank Adaptation (LoRA) tuning [28] on two publicly available LLMs.
In this section, we describe the base model and the process of LoRA tuning.

§.§ Models

We use two models: a Japanese-based model and an English-based model.
The models we use are the Japanese-based OpenCALM-7B (hereafter CALM) and the English-based LLaMA 7B.
CALM is a model with 7 billion parameters released by CyberAgent [<https://huggingface.co/cyberagent/open-calm-7b>].
It is pre-trained on Japanese Wikipedia and Common Crawl using the GPT-NeoX architecture [8].
For the English-based model, we use the 7B model of LLaMA [13] (hereafter LLaMA 7B), which is released by Meta [Strictly speaking, although it was not initially open-source, it has become available under certain licenses].

Due to the differences in characteristics between the Japanese-based CALM and the English-based LLaMA 7B, we use llm-japanese-dataset-vanilla, which we constructed above, for CALM and llm-japanese-dataset for LLaMA 7B as training data.
For tuning CALM, we use version v0.1.0 as the training data, which excludes the JQAC and Wikipedia Typo datasets.
This is done to align with the model constructed in the literature [25], ensuring dataset consistency with the exception of not including English.

We train LLaMA 7B on the entire llm-japanese-dataset v0.1.0, following the methods outlined in [25].
We adopt the same input format as described in [25].
From this point forward, the tuned CALM will be referred to as “Stormy,” and the LLaMA 7B as “Instruct LLaMA 7B.”

§.§ LoRA Tuning

LLMs, having a large number of parameters, require GPU resources not only for pre-training but also for fine-tuning.
In this study, we use LoRA [28] as a method for tuning LLMs without significantly reducing accuracy.
In LoRA, only the difference between the initial and updated LLM parameters, represented with small-scale parameters, is calculated.
Consider an example of updating the parameter matrix $W_0 \in \mathbb{R}^{d\times k}$ of a certain linear layer that LLM has.
Instead of training $W_0$ directly, initialize the difference $\Delta W \in \mathbb{R}^{d\times k}$ to $W_0$ with a zero matrix, update the difference $\delta W$, and proceed with training by updating the parameters to $W_0 + \Delta W$.
Here, we set $\Delta W= BA$ where $B \in \mathbb{R}^{d \times r}$ and $A \in \mathbb{R}^{r \times k}$ are matrices of rank $r \ll \min (d,k)$.
This can reduce the number of learnable parameters from $dk$ to $(d+k)r$.

The primary parameters utilized in the experiment are shown in Table <ref>.
For comparison, we also mention the model that Instruct LLaMA 13B [25], which was LoRA-tuned with llm-japanese-dataset v0.1.0.

We used PEFT [29] and DeepSpeed ZeRO [30] for implementation.
The code is available at <https://github.com/retarfi/jallm>.

§ EVALUATING CONSTRUCTED MODELS

We evaluate the tuned models both quantitatively and qualitatively.
From the quantitative perspective, we evaluate from two perspectives.
The first is accuracy derived from the likelihood of choices in text classification tasks with JNLI and MARC-ja.
JNLI and MARC-ja are tasks from JGLUE [31].
Further details are described in Section <ref>.
The second is perplexity using question-answering data that is not included in the dataset constructed in this study.
From the qualitative perspective, we qualitatively evaluate the output for several prompts.
The temperature parameter for generation is 0.0, and the repetition penalty [32] is 1.05 for CALM and Stormy and 1.0 for Instruct LLaMA 7B and LLaMA 7B.
We use 5 prompts for input to the models, which are the same as those used in the literature [25].
We also conduct evaluation experiments on LLaMA 13B and Instruct LLaMA 13B, which  was instruction tuned for LLaMA 13B, constructed in the study [25] as well.

§.§ Accuracy

Another evaluation is performed by JNLI and MARC-ja included in JGLUE [31].
JNLI is a task to choose the relationship that the premise sentence shows to the sentence pair of the hypothesis from three options: entailment, contradiction, and neutral.
MARC-ja is a task to choose either “positive” or “negative” in Japanese for product reviews and is constructed using the Japanese part of the Multilingual Amazon Reviews Corpus (MARC)  [33].
In addition to these, JGLUE includes JCommonsenseQA, which questions common sense, and JSQuAD, which is an extraction task.
However, these data are included in the llm-japanese-dataset v0.1.0, which is used for instruction LoRA tuning.
Therefore, they were considered inappropriate as evaluation tasks and excluded.

For the implementation of the experiment, we use the Japanese evaluation branch [<https://github.com/Stability-AI/lm-evaluation-harness/tree/jp-stable>] of Stability-AI/lm-evaluation-harness [34].
Aligning with lm-evaluation-harness, we use the prompt version that achieves the best performance.
We adopt v0.2 for Stormy and v0.3 for the others, such as CALM, Instruct LLaMA 7B, LLaMA 7B, Instruct LLaMA 13B, and LLaMA 13B.
Detailed prompts are described in the [sec:prompt-jnli-marcja]Appendix.

For the input prompt, we compare the likelihood of the strings of each task's choicesand take the highest one as the model's output.
In JNLI, the three choices are entailment, contradiction, and neutral, and in MARC-ja, the two choices are “positive” and “negative” in Japanese, and the model outputs the choice with the highest likelihood of output.
Therefore, outputs other than the choices are not considered.
We evaluate for each of 1-shot, 2-shot, and 3-shot, which show one, two, or three examples in the input, respectively.

Results of the evaluation experiment. $^*$ indicates that there were data in the evaluation dataset that exceeded the input length of LoRA tuning (Stormy is 300, Instruct LLaMA 7B and Instruct LLaMA 13B are 256). $^{\dagger}$ indicates that there were data in the evaluation dataset that exceeded the maximum input length of the model (both CALM-based and LLaMA-based are 2,048). The highest-performing areas for each task are indicated in bold.

3cJNLI     3cMARC-ja     VQA
(lr)2-4 (lr)5-7
Model     1-shot     2-shot     3-shot     1-shot     2-shot     3-shot     Perplexity
Stormy (Instruct CALM)     0.459     0.508     0.475     0.468     0.828$^*$     0.784$^*$     29.9

CALM[1]     0.294     0.331     0.314     0.781     0.836     0.856     246.6

Instruct LLaMA 7B     0.398$^*$     0.454$^*$     0.479$^{*\dagger}$     0.795$^*$     0.829$^*$     0.847$^*$     68.5

LLaMA 7B[13]     0.171     0.273     0.303$^{\dagger}$     0.839     0.848     0.852     1,499

Instruct LLaMA 13B [25]    0.302$^*$     0.302$^*$     0.302$^{*\dagger}$     38.8      0.859$^*$     0.855$^*$     0.855$^*$

LLaMA 13B [13]     0.316     0.281     0.263$^{\dagger}$     0.855     0.855     0.855     971.5

§.§ Perplexity

Perplexity, as defined by  [35], is the exponential of the average negative log-likelihood.
The lower the value, the higher the probability that the words in the dataset are correctly output.
Given a tokenized sequence $X=(x_0, x_1, \cdots, x_t)$, the perplexity of $X$ is represented by Equation (<ref>).

\begin{equation}\label{eq:ppl}
\mathrm{Perplexity}(X) = \exp \left\{-\frac{1}{t}\sum_{i}^{t} \log p_{\theta}(x_i|x_{<i})\right\}
\end{equation}

Here, $\log p_{\theta}(x_i|x_{<i})$ is the log-likelihood of the $i$-th token given the preceding tokens $x_{<i}$.

In this study, we measure perplexity using the Japanese Visual Question Answering (VQA) dataset [36], which is not included in the llm-japanese-dataset v0.1.0 used for tuning the language model.
Although this VQA dataset is a question-answering task performed by looking at presented images, it is conjectured that models with a high probability of predicting the correct response sentence are more natural.
We convert 793,664 question and answer pairs extracted from the VQA dataset into prompt format and input them.
An example of the input is shown below.

Example in VQA with Japanese-based Model
9.5pt13ptWrite a response to answer the following question.

### Question:

What color is the airplane's body?

### Response:

White [footnotecommon1]

It should be noted that the LLaMA-based model uses English for system messages.
Therefore, following the literature [25], the above example is modified as follows.

Example in VQA with English-based Model
9.5pt13ptWrite a response to answer the following question.

### Question:

What color is the airplane's body? [footnotecommon1]

### Response:

White [footnotecommon1]

The calculation of perplexity is not performed on the input to the model and is only applied to the response.
In other words, in the above example, perplexity is calculated only for the token corresponding to the output “white.”

§ RESULTS AND DISCUSSION

§.§ Quantitative Evaluation

The results of the evaluation experiment are shown in Table <ref>.
In the evaluation by JNLI, the accuracy of Stormy was the highest across 1-shot, 2-shot, and 3-shot settings.
Even though the llm-japanese-dataset v0.1.0 does not include a dataset equivalent to implication relation recognition, the performance seems to have been improved by solving various tasks as in [16].
The improvement in performance on tasks not present in the dataset by using instruction tuning across various tasks aligns with the findings in the literature [16, 17].
Japanese instruction datasets are valuable in the point of having constructed similar datasets for languages other than English.
The performance of Stormy and Instruct LLaMA 7B, which performed instruction tuning on CALM and LLaMA 7B, respectively, improved, showing the effect of instruction tuning.
However, the effect of instruction tuning in LLaMA 13B was relatively small.
This is likely because instruction tuning in Instruct LLaMA 13B was performed for only one epoch.
Performance might improve with more training epochs.
When comparing two Instruct LLaMA models with different numbers of parameters, even though there was a difference in the number of training epochs, Instruct LLaMA 7B showed a stronger effect from instruction tuning.
This is considered to be because the smaller model size facilitates more effective training.
It has been reported that larger model sizes result in better performance on downstream tasks [7, 10, 13].
However, it is possible that tuning a smaller model might yield better performance under the same computational resources for instruction tuning.

In the evaluation by MARC-ja, there was no performance improvement by instruction tuning in all of 1-shot, 2-shot, and 3-shot, or the performance became worse.
This phenomenon has also been reported in [37, 16].
The performance might be improved by adopting more various tasks widely as instruction data as in  [16].
As well as MARC-ja, there are also datasets related to sentiment that can be incorporated in Japanese, such as the chABSA-dataset[<https://github.com/chakki-works/chABSA-dataset>] (ABSA stands for Aspect-Based Sentiment Analysis).
The decrease in accuracy could be suppressed by additionally training these datasets.
Another possible reason why the performance did not improve in the LLaMA-based models is the input length of instruction tuning in this study.
While the LLaMA-based model itself can input up to 2,048 tokens and pre-training is performed at this length, in this study, the input length is limited to 256 tokens.
Therefore, in data where long tokens are input, the effect of instruction tuning may not have been demonstrated.
Extending the input length of instruction tuning is a future issue.

In the evaluation of perplexity using VQA, all the instruct-tuned models showed improved performance with reduced perplexity due to tuning using instruction data.
Language models adopting the decoder architecture are trained to increase the probability of correctly predicting the next token in the input.
Therefore perplexity is trained to decrease.
However, the reason for the reduction in perplexity by instruction tuning might be attributed to differences in the input data.
While a language model predicts the next token for consecutive sequences in pre-training, it predicts tokens sequentially in response to a given question in instruction tuning.
Since the format of input and output in instruction tuning matches the question-answering in VQA used in this experiment, it can be inferred that the model became more accustomed to producing answers by instruction tuning, leading to a reduction (performance improvement) in perplexity.

The improvement in perplexity was particularly noticeable in the LLaMA-based models.
A link with Japanese is considered to have been created and the performance improved by training using instruction data including translation data, even for models other than Japanese, such as English.
Among the six models, the one with the highest perplexity and the worst performance was LLaMA 7B.
This is thought to be due to the fact that it is an English-based model and has fewer model parameters than LLaMA 13B.
On the other hand, the model that showed the best performance with the lowest perplexity was Stormy.
The performance was improved by further instruction tuning for CALM, which is a model of Japanese.
Comparing CALM, LLaMA 7B, and LLaMA 13B, which were the base models for tuning, the Japanese-based CALM showed the highest performance.

In terms of the effect of instruction tuning from the perspective of model size, the literature [16] reported that for models larger than 68B, the effects of instruction tuning were observed in downstream tasks.
However, they also reported for models smaller than 8B, instruction tuning paradoxically degraded performance in downstream tasks.
In the results of the MARC-ja experiments in this study, no effect of instruction tuning was observed for all models of 7B and 13B, while for JNLI, the positive effects of instruction tuning were observed in all models.
This effect was observed in both Japanese-based CALM and English-based LLaMA models.
This suggests that, in non-English languages or when tuning English models to them, instruction tuning does not necessarily have negative effects for smaller models, and could even contribute to performance enhancement.

in comparison with prior research [16, 38], there are fewer types of tasks.
This might have led to a potential constraint in performance improvement.
For instance, when compared to FLAN [16], tasks like simplification and correction have been newly added, while tasks like natural language inference, sentiment, and paraphrase lack.
In this study, although the experiments were conducted using the 5 task types shown in Figure <ref>, consistent results were observed even in a non-English language like Japanese.
Expanding the variety of tasks will be a challenge for future research.

Regarding the base language of the model, there was no difference in terms of performance trends between the Japanese-based model and the English-based model; performance improved in VQA and JNLI, but not in MARC-ja.
The results show that using a Japanese instruction dataset can enhance performance in Japanese tasks for both English-based and Japanese-based models.
Except for the fact that translation tasks were used in the instruction tuning data of the LLaMA-derived model, the other tasks used in Stormy and Instruct LLaMA are the same.
How the translation task impacts both English-based and Japanese-based models remains a future research topic.

As discussed in the results for JNLI, while instruction tuning is effective for unseen tasks, the inclusion of similar tasks in the dataset is considered to have a substantial impact on performance improvement [16].
Based on this, it can be inferred that by adding tasks related to natural language inference for JNLI and sentiment for MARC-ja, the performance on JNLI and MARC-ja tasks would improve more.
The tasks evaluated in this study evaluate how much the model can output for a certain output (although it is consistent with the evaluation method in [6]), and do not consider the actual output of the model.
For a more detailed comparison, it is also a future task to evaluate using actual outputs.
In addition, it will be necessary in the future to evaluate from the perspective of human preference [39, 40], not just focusing on the task's correctness.

§.§ Qualitative Evaluation

The following shows the responses of the models used in this study, such as Stormy, CALM, Instruct LLaMA 7B, and LLaMA 7B.
For responses of Instruct LLaMA 13B and LLaMA 13B to the input shown below, please refer to the literature [25].

Comparison of Responses (1)
9.5pt13pt### Input:

Who are you? [footnotecommon1]

### Output (Stormy):

I am my wife, and I love her. [footnotecommon1]

### Output (CALM):

I am Nick M. Kelemel. I have degrees in computer science and mathematics, and I am currently working as a researcher. [footnotecommon1]

### Output (Instruct LLaMA 7B):

What are you doing? [footnotecommon1]

### Output (LLaMA 7B):

Who are you? [footnotecommon1]

Comparison of Responses (2)
9.5pt13pt### Input:

Please tell me how to get to Osaka from Tokyo. [footnotecommon1]

### Output (Stormy):

Depart from Tokyo by plane. When you arrive in Osaka, transfer to the Shinkansen and go to Nagoya. From Nagoya, take the Kintetsu Limited Express. [footnotecommon1]

### Output (CALM):

Which is better, train or Shinkansen?
“Train” refers to all types of transportation, such as JR trains and private railways.
“Shinkansen” refers to the Tokaido and Sanyo Shinkansen that run between Tokyo and Shin-Osaka.
“Airplane” typically refers to the route between Haneda and Itami.
“Bus” refers to the Toei buses that operate in Tokyo.
“Car” includes not only private cars but also taxis and rental cars.
“Bicycle” includes electric-assisted bicycles.
“Walking,” “jogging,” and “strolling” are excluded. [footnotecommon1]

### Output (Instruct LLaMA 7B):

Please tell me how to get to Tokyo from Osaka. [footnotecommon1]

### Output (LLaMA 7B):

Please tell me how to get to Osaka from Tokyo. [footnotecommon1]

Comparison of Responses (3)
9.5pt13pt### Input:

Where is the University of Tokyo? [footnotecommon1]

### Output (Stormy):

The University of Tokyo is a national university located in Bunkyo-ku, Tokyo. [footnotecommon1]

### Output (CALM):

The University of Tokyo is located at 7-3-1 Hongo, Bunkyo-ku, Tokyo. The latitude and longitude of the University of Tokyo are 35.676044, 135.869422.

##Answer: What do you use to get to that address? (Maps or Google Map, etc.)

##Explanation: What mode of transportation should I use to get to that address?

##Answer: Which is better to use, train or bus?

##Explanation: If you use the JR line, please get off at the “Yamanote Line.” The JR line goes to “Tokyo” station.

##Answer: Where should I go from Tokyo station?

##Explanation: The trains you take from “Tokyo Station” are the “Tokaido Shinkansen,” “Tohoku, Joetsu, Hokuriku Shinkansen” and “Limited Express Hitachi.”

##Answer: Which is faster and cheaper, the Joban Line or the Shinkansen?

##Explanation: The Shinkansen is faster. However, the price is different.

##Answer: I don't have money, what should I do?

##Explanation: First, please prepare money. If you have a credit card, you can use it.

##Answer: How should I pay?

##Explanation: You can pay by card. VISA card [footnotecommon1]

### Output (Instruct LLaMA 7B):

The University of Tokyo is in Tokyo. [footnotecommon1]

### Output (LLaMA 7B):

Where is the University of Tokyo? [footnotecommon1]

(Authors' note: The correct address is 7-3-1 Hongo, Bunkyo-ku, Tokyo.)

Comparison of Responses (4)
9.5pt13pt### Input:

The phone is ringing. What should I do? [footnotecommon1]

### Output (Stormy):

Should you answer the phone? Or should you put it on hold? [footnotecommon1]

### Output (CALM):

Press the hold button, answer the phone, or call the answering service. When you hear the ringtone, reply within 10 seconds. If there is no response, try calling again. If that still doesn't work, proceed to the next step.
Press `0' to end the call.
Press `*' after the ringtone. This will enable the call. [footnotecommon1]

### Output (Instruct LLaMA 7B):

The phone is ringing. What should I do? [footnotecommon1]

### Output (LLaMA 7B):

The phone is ringing. What should I do? [footnotecommon1]

Comparison of Responses (5)
9.5pt13pt### Input:

What are the three major festivals in Kyoto? [footnotecommon1]

### Output (Stormy):

Aoi Festival, Gion Festival, Jidai Festival [footnotecommon1]

### Output (CALM):

The three are Gion Festival, Aoi Festival, and Jidai Festival. They are also referred to as the three major festivals of Kyoto. [footnotecommon1]

(Authors' Note: “  #N/A” continues from here.)

### Output (Instruct LLaMA 7B):

What are the three major festivals in Kyoto? [footnotecommon1]

### Output (LLaMA 7B):

What are the three major festivals in Kyoto? [footnotecommon1]

(Authors' note: The correct answer is Aoi, Gion, Jidai festivals.)

Stormy, which was instruct-tuned from CALM, demonstrates a more natural response format.
On the other hand, the difference between Instruct LLaMA 7B and LLaMA 7B appears to be minimal, with only a slight improvement in the accuracy of response comparison (3).
According to the literature [25], the small improvement in LLaMA 13B's 1 epoch tuning was attributed to the limited amount of training.
However, despite 5 epochs of tuning on LLaMA 7B, Instruct LLaMA 7B did not show significant improvement.
This result contrasts with the trend observed in the quantitative evaluations discussed in Section <ref>.
This difference suggests that instruction tuning alone may not lead to significant improvements.
Not only through instruction tuning, but also by additional pre-training to accumulate knowledge about the target language (in this case, Japanese) and then performing instruction tuning, there is a potential to improve performance in the target language [41].
Various methods can be considered for pre-training, including pre-training from scratch solely in Japanese or conducting additional pre-training in Japanese using English or multilingual models.
Hence, exploring methods to achieve high performance in languages other than English will be a future challenge.
Moreover, the difference between the trend observed in the qualitative evaluation and that of the quantitative evaluation highlights the importance of evaluating qualitative performance not only based on simple metrics like likelihood or perplexity generated by the model but also based on the actual output strings.

§ RELATED WORK

§.§ Pre-training Models

The Transformer [1], a crucial component of large language models (LLMs), consists of two architectures: encoder and decoder.
Models such as BERT [2], RoBERTa [3], and DeBERTa [42, 43] utilize the Transformer's encoder.
In recent LLMs, the decoder (causal decoder) is primarily used.
The GPT series [4, 5, 6, 44] is a representative language model with a decoder architecture.
There are also many proposed models, such as OPT [7], GPT-NeoX-20B [8], Gopher [45], PaLM [10], BLOOM [11], Pythia [12], and LLaMA series [13, 14].
Although relatively few, there is also T5 [46] as an encoder-decoder architecture, and Flan T5 [16] has been proposed as an extension of it.

§.§ Tuning after Pre-training

Through pre-training, LLMs acquire the ability to solve various tasks.
However, there is an increasing number of cases where fine-tuning is performed to align more with specific purposes, such as dialogue responses.
There are mainly two approaches for this fine-tuning: alignment tuning and instruction tuning.
Alignment tuning is a tuning to aim for outputs more in line with human preferences [37].
Through alignment tuning, LLMs are adjusted to produce outputs that align with human values, such as being helpful, honest, and harmless.
In recent LLMs, reinforcement learning (RL) [47], especially Proximal Policy Optimization (PPO) [48], is used to learn from human-labeled response preference rankings.
Instruction tuning is generally a method of fine-tuning LLMs with datasets in natural language format, supervised [37], and performed using various tasks (multi-task) [17].
It has been shown that instruction tuning can demonstrate excellent performance even for unknown tasks [16, 19, 17].
In instruction tuning, instructions that request the output of the LLM are described in the input, and training is performed so that the LLM outputs the expected response.
It has been shown that the task-explanation part is particularly decisive in the performance of the LLM that improves through instruct tuning [16].
If tuning is performed with a dataset that is closer to traditional supervised learning by removing the explanation about the task, the performance will significantly decrease compared to not removing it.
Most cases of instruct tuning are performed with formatted existing datasets for various tasks in natural language format for instruction tuning datasets.
Specifically, labeled datasets are applied with instructions written by humans explaining the task, explaining the direction of the output, and instructing the LLM to understand the task from the input [17, 16, 38].
Other construction methods include examples of constructing datasets using the output of ChatGPT or GPT-4 [49, 39, 22][<https://huggingface.co/datasets/RyokoAI/ShareGPT52K>]$^{,}$[<https://github.com/teknium1/GPTeacher>], and there are few examples of constructing datasets manually [20].

§.§ Tuning of LLMs

Efficient tuning in LLMs with many parameters is attracting attention to adapt LLMs to various downstream tasks.
In particular, LoRA [28] is widely applied to open-source LLMs.
For example, Alpaca-LoRA [50] uses LoRA to tune LLaMA 7B as a lightweight tuning version of Alpaca [22].
Also, AdaLoRA [51] changes the value of the rank in LoRA.
This adjustment occurs according to the layer to be applied.

Other efficient tuning methods include adding an Adapter layer to the existing layers [52, 53, 54], and prompt tuning [55, 56], which fixes the weights of the pre-trained model, adds trainable parameters to the prompt instructions.

§ CONCLUSION

We constructed an instruction dataset for Japanese-based LLMs (Large Language Models).
The dataset excludes any translation data originally present in the llm-japanese-dataset and introduces additional tasks to the existing ones.
We performed LoRA tuning on LLMs pre-trained in both Japanese and English, respectively.
The tuning was done using Japanese instruction data.
We evaluated the tuned models from both quantitative and qualitative perspectives.
The results show that tuning with Japanese instruction data improves performance in quantitative evaluations.
In particular, the results indicate that not only Japanese-based models but also English-based models can be tuned in Japanese using the Japanese instruction dataset.
Furthermore, even with smaller model sizes like 7B or 13B, instruction tuning can sometimes improve performance in downstream tasks, suggesting a result different from prior research.

Future research can address not only comparing the likelihood of the current model's output, but also using the actual output in the evaluation of the model.
Additionally, it could include evaluation from the perspective of human preference in Japanese.

§ ACKNOWLEDGMENT

This work was supported in part by JSPS KAKENHI Grant Number JP21K12010 and JST PRESTO Grant Number JPMJPR2267.

[1]
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez,
Ł. Kaiser, and I. Polosukhin, “Attention Is All You Need,” in
Advances in Neural Information Processing Systems, vol. 30, 2017, pp.

[2]
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of Deep
Bidirectional Transformers for Language Understanding,” in
Proceedings of the 2019 Conference of the North American Chapter of
the Association for Computational Linguistics.1em plus 0.5em minus
0.4emAssociation for Computational Linguistics, 2019, pp. 4171–4186.

[3]
Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis,
L. Zettlemoyer, V. Stoyanov, and P. G. Allen, “RoBERTa: A Robustly
Optimized BERT Pretraining Approach,” 2019. [Online]. Available:

[4]
A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever, “Improving Language
Understanding by Generative Pre-Training,” 2018. [Online]. Available:

[5]
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language
Models are Unsupervised Multitask Learners,” 2019. [Online]. Available:

[6]
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal,
A. Neelakantan, P. Shyam, G. Sastry, A. Askell et al., “Language
Models are Few-Shot Learners,” Advances in Neural Information
Processing Systems, vol. 33, pp. 1877–1901, 2020.

[7]
S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab,
X. Li, X. V. Lin et al., “OPT: Open Pre-trained Transformer Language
Models,” 2022. [Online]. Available: <https://arxiv.org/abs/2205.01068>

[8]
S. Black, S. Biderman, E. Hallahan, Q. Anthony, L. Gao, L. Golding, H. He,
C. Leahy, K. McDonell, J. Phang et al., “GPT-NeoX-20B: An
Open-Source Autoregressive Language Model,” in Proceedings of
BigScience Episode #5 – Workshop on Challenges & Perspectives in
Creating Large Language Models.1em plus 0.5em minus 0.4emAssociation for Computational Linguistics, 2022, pp. 95–136.

[9]
Y. Tay, M. Dehghani, V. Q. Tran, X. Garcia, J. Wei, X. Wang, H. W. Chung,
D. Bahri, T. Schuster, S. Zheng et al., “UL2: Unifying Language
Learning Paradigms,” in International Conference on Learning
Representations, 2023.

[10]
A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham,
H. W. Chung, C. Sutton, S. Gehrmann et al., “PaLM: Scaling Language
Modeling with Pathways,” 2022. [Online]. Available:

[11]
T. L. Scao, A. Fan, C. Akiki, E. Pavlick, S. Ilić, D. Hesslow,
R. Castagné, A. S. Luccioni, F. Yvon, M. Gallé et al.,
“BLOOM: A 176B-Parameter Open-Access Multilingual Language Model,” 2022.
[Online]. Available: <https://arxiv.org/abs/2211.05100>

[12]
S. Biderman, H. Schoelkopf, Q. Anthony, H. Bradley, K. O'Brien, E. Hallahan,
M. A. Khan, S. Purohit, U. S. Prashanth, E. Raff et al., “Pythia: A
Suite for Analyzing Large Language Models Across Training and Scaling,”
2023. [Online]. Available: <https://arxiv.org/abs/2304.01373>

[13]
H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix,
B. Rozière, N. Goyal, E. Hambro, F. Azhar et al., “LLaMA: Open
and Efficient Foundation Language Models,” 2023. [Online]. Available:

[14]
H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei,
N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale et al., “Llama 2:
Open foundation and fine-tuned chat models,” 2023. [Online]. Available:

[15]
J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama,
M. Bosma, D. Zhou, D. Metzler et al., “Emergent abilities of large
language models,” Transactions on Machine Learning Research, 2022.

[16]
J. Wei, M. Bosma, V. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and
Q. V. Le, “Finetuned language models are zero-shot learners,” in
International Conference on Learning Representations, 2022.

[17]
V. Sanh, A. Webson, C. Raffel, S. Bach, L. Sutawika, Z. Alyafeai, A. Chaffin,
A. Stiegler, A. Raja, M. Dey et al., “Multitask Prompted Training
Enables Zero-Shot Task Generalization,” in International Conference
on Learning Representations, 2022.

[18]
A. Köpf, Y. Kilcher, D. von Rütte, S. Anagnostidis, Z.-R. Tam, K. Stevens,
A. Barhoum, N. M. Duc, O. Stanley, R. Nagyfi et al., “Openassistant
conversations – democratizing large language model alignment,” 2023.
[Online]. Available: <https://arxiv.org/abs/2304.07327>

[19]
H. W. Chung, L. Hou, S. Longpre, B. Zoph, Y. Tay, W. Fedus, Y. Li, X. Wang,
M. Dehghani, S. Brahma et al., “Scaling Instruction-Finetuned
Language Models,” 2022. [Online]. Available:

[20]
Databricks, “Dolly,” <https://github.com/databrickslabs/dolly>, 2023.

[21]
Vicuna, “Vicuna: An Open-Source Chatbot Impressing GPT-4 with 90% ChatGPT
Quality,” <https://vicuna.lmsys.org/>, 2023.

[22]
R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and
T. B. Hashimoto, “Stanford Alpaca: An Instruction-following LLaMA model,”
<https://github.com/tatsu-lab/stanford_alpaca>, 2023.

[23]
G. Zhang, Y. Shi, R. Liu, R. Yuan, Y. Li, S. Dong, Y. Shu, Z. Li, Z. Wang,
C. Lin, W. Huang, and J. Fu, “Chinese open instruction generalist: A
preliminary release,” 2023. [Online]. Available:

[24]
Y. Cui, Z. Yang, and X. Yao, “Efficient and effective text encoding for
chinese llama and alpaca,” 2023. [Online]. Available:

[25]
M. Hirano, M. Suzuki, and H. Sakaji, “llm-japanese-dataset v0: Construction
of Japanese Chat Dataset for Large Language Models and its Methodology,”
2023. [Online]. Available: <https://arxiv.org/abs/2305.12720>

[26]
Y. Tanaka, Y. Murawaki, D. Kawahara, and S. Kurohashi, “Improving a Japanese
Typo Dataset and Typo Correction System Based on Wikipedia’s Revision
History,” in Proceedings of the Twenty-seventh Annual Meeting of the
Association for Natural Language Processing, 2021, pp. 1540–1545, (in
Japanese). [Online]. Available:

[27]
H. Tanioka, K. Kimura, K. Takaoka, R. Nakatani, and Y. Uchida, “Automatic
Generation of Japanese Question-Answering Pairs,” in Fourth Asia
Pacific Corpus Linguistics Conference (APCLC 2018), 2018.

[28]
E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and
W. Chen, “LoRA: Low-Rank Adaptation of Large Language Models,” in
International Conference on Learning Representations, 2022, pp. 1–13.

[29]
S. Mangrulkar, S. Gugger, L. Debut, Y. Belkada, and S. Paul, “PEFT:
State-of-the-art Parameter-Efficient Fine-Tuning methods,”
https://github.com/huggingface/peft, 2022.

[30]
S. Rajbhandari, J. Rasley, O. Ruwase, and Y. He, “ZeRO: Memory Optimizations
toward Training Trillion Parameter Models,” in SC20: International
Conference for High Performance Computing, Networking, Storage and Analysis,
2020, pp. 1–16.

[31]
K. Kurihara, D. Kawahara, and T. Shibata, “JGLUE: Japanese General Language
Understanding Evaluation,” in Proceedings of the Thirteenth Language
Resources and Evaluation Conference, 2022, pp. 2957–2966.

[32]
N. S. Keskar, B. McCann, L. R. Varshney, C. Xiong, and R. Socher, “CTRL: A
Conditional Transformer Language Model for Controllable Generation,” 2019.
[Online]. Available: <http://arxiv.org/abs/1909.05858>

[33]
P. Keung, Y. Lu, G. Szarvas, and N. A. Smith, “The Multilingual Amazon
Reviews Corpus,” in Proceedings of the 2020 Conference on Empirical
Methods in Natural Language Processing, 2020.

[34]
L. Gao, J. Tow, S. Biderman, S. Black, A. DiPofi, C. Foster, L. Golding,
J. Hsu, K. McDonell, N. Muennighoff et al., “A framework for few-shot
language model evaluation,” 2021. [Online]. Available:

[35]
F. Jelinek, R. L. Mercer, L. R. Bahl, and J. K. Baker, “Perplexity—a measure
of the difficulty of speech recognition tasks,” The Journal of the
Acoustical Society of America, vol. 62, no. S1, pp. S63–S63, 1977.

[36]
N. Shimizu, N. Rong, and T. Miyazaki, “Visual Question Answering Dataset for
Bilingual Image Understanding: A Study of Cross-Lingual Transfer Using
Attention Maps,” in Proceedings of the 27th International Conference
on Computational Linguistics.1em plus 0.5em minus 0.4emAssociation for Computational Linguistics, 2018, pp. 1918–1928.

[37]
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang,
S. Agarwal, K. Slama, A. Gray et al., “Training language models to
follow instructions with human feedback,” in Advances in Neural
Information Processing Systems, A. H. Oh, A. Agarwal, D. Belgrave, and
K. Cho, Eds., 2022.

[38]
Y. Wang, S. Mishra, P. Alipoormolabashi, Y. Kordi, A. Mirzaei, A. Naik,
A. Ashok, A. S. Dhanasekaran, A. Arunkumar, D. Stap et al.,
“Super-NaturalInstructions: Generalization via Declarative Instructions on
1600+ NLP Tasks,” in Proceedings of the 2022 Conference on Empirical
Methods in Natural Language Processing.1em plus 0.5em minus
0.4emAssociation for Computational Linguistics, 2022, pp. 5085–5109.

[39]
B. Peng, C. Li, P. He, M. Galley, and J. Gao, “Instruction Tuning with
GPT-4,” 2023. [Online]. Available: <https://arxiv.org/abs/2304.03277>

[40]
C. Zhou, P. Liu, P. Xu, S. Iyer, J. Sun, Y. Mao, X. Ma, A. Efrat, P. Yu, L. Yu
et al., “LIMA: Less Is More for Alignment,” 2023. [Online].
Available: <https://arxiv.org/abs/2305.11206>

[41]
Z.-X. Yong, H. Schoelkopf, N. Muennighoff, A. F. Aji, D. I. Adelani,
K. Almubarak, M. Saiful Bari, L. Sutawika, J. Kasai, A. Baruwa et al.,
“BLOOM+1: Adding language support to BLOOM for Zero-Shot prompting,”
2022. [Online]. Available: <https://arxiv.org/abs/2212.09535>

[42]
P. He, X. Liu, J. Gao, and W. Chen, “DeBERTa: Decoding-enhanced BERT with
Disentangled Attention,” in International Conference on Learning
Representations, 2021.

[43]
P. He, J. Gao, and W. Chen, “DeBERTaV3: Improving DeBERTa using ELECTRA-Style
Pre-Training with Gradient-Disentangled Embedding Sharing,” in
International Conference on Learning Representations, 2023.

[44]
OpenAI, “GPT-4 Technical Report,” 2023. [Online]. Available:

[45]
J. W. Rae, S. Borgeaud, T. Cai, K. Millican, J. Hoffmann, F. Song,
J. Aslanides, S. Henderson, R. Ring, S. Young et al., “Scaling
Language Models: Methods, Analysis & Insights from Training Gopher,” 2022.
[Online]. Available: <https://arxiv.org/abs/2112.11446>

[46]
C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou,
W. Li, and P. J. Liu, “Exploring the Limits of Transfer Learning with a
Unified Text-to-Text Transformer,” Journal of Machine Learning
Research, vol. 21, no. 140, pp. 1–67, 2020.

[47]
P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei,
“Deep reinforcement learning from human preferences,” in Advances
in neural information processing systems, vol. 30, 2017, pp. 4299–4307.

[48]
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal
Policy Optimization Algorithms,” 2017. [Online]. Available:

[49]
S. Chaudhary, “Code Alpaca: An Instruction-following LLaMA model for code
generation,” <https://github.com/sahil280114/codealpaca>, 2023.

[50]
E. Wang, “Alpaca-LoRA,” <https://github.com/tloen/alpaca-lora>, 2023.

[51]
Q. Zhang, M. Chen, A. Bukharin, P. He, Y. Cheng, W. Chen, and T. Zhao,
“Adaptive budget allocation for parameter-efficient fine-tuning,” in
International Conference on Learning Representations, 2023.

[52]
N. Houlsby, A. Giurgiu, S. Jastrzebski, B. Morrone, Q. de Laroussilhe,
A. Gesmundo, M. Attariyan, and S. Gelly, “Parameter-efficient transfer
learning for nlp,” 2019. [Online]. Available:

[53]
Z. Lin, A. Madotto, and P. Fung, “Exploring Versatile Generative Language
Model Via Parameter-Efficient Transfer Learning,” in Findings of the
Association for Computational Linguistics: EMNLP 2020.1em plus 0.5em
minus 0.4emOnline: Association for Computational Linguistics, Nov.
2020, pp. 441–459.

[54]
Z. Hu, Y. Lan, L. Wang, W. Xu, E.-P. Lim, R. K.-W. Lee, L. Bing, X. Xu, and
S. Poria, “LLM-Adapters: An Adapter Family for Parameter-Efficient
Fine-Tuning of Large Language Models,” 2023. [Online]. Available:

[55]
X. L. Li and P. Liang, “Prefix-tuning: Optimizing continuous prompts for
generation,” in Proceedings of the 59th Annual Meeting of the
Association for Computational Linguistics and the 11th International Joint
Conference on Natural Language Processing (Volume 1: Long Papers).1em
plus 0.5em minus 0.4emAssociation for Computational Linguistics, 2021,
pp. 4582–4597.

[56]
B. Lester, R. Al-Rfou, and N. Constant, “The power of scale for
parameter-efficient prompt tuning,” in Proceedings of the 2021
Conference on Empirical Methods in Natural Language Processing.1em
plus 0.5em minus 0.4emAssociation for Computational Linguistics, 2021,
pp. 3045–3059.

Prompts Used in JNLI and MARC-ja
Example of 1-shot prompt used in JNLI (v0.2)
9.5pt13ptPlease answer the relationship between the premise and the hypothesis from[footnotecommon1] entailment, contradiction, and[footnotecommon1] neutral.

- If the hypothesis can be derived from the premise using logical or common sense knowledge, output[footnotecommon1] entailment

- If the premise and the hypothesis are incompatible, output[footnotecommon1] contradiction

- If neither of the above, output[footnotecommon1] neutral

Premise: Two women are jumping to catch a frisbee in the grass.

Hypothesis: The two women are holding a tray with donuts on it.

Relationship:[footnotecommon1] entailment

Premise: There are two children, and bananas and kiwis are placed next to the mixer.

Hypothesis: There are children with droppers at the table where the mixer is placed.

Relationship: [footnotecommon1]

Although the same instructions are repeated within the same prompt, the template from the implementation reference (<https://github.com/Stability-AI/lm-evaluation-harness/tree/jp-stable>) is used as is.

Example of 1-shot prompt used in JNLI (v0.3) [footnotecommon2]
9.5pt13ptBelow is a combination of instructions explaining the task and contextual inputs. Write a response that adequately meets the request.

### Instructions:

Please answer the relationship between the given premise and hypothesis.

Choose your output from the following: [footnotecommon1]

### Input:

Premise: Two women are jumping to catch a frisbee in the grass.

Hypothesis: The women are trying to catch a frisbee.

### Response: [footnotecommon1]

### Instructions:

Please answer the relationship between the given premise and hypothesis.

Choose your output from the following: [footnotecommon1]

### Input:

Premise: There are two children, and bananas and kiwis are placed next to the mixer.

Hypothesis: There are children with droppers at the table where the mixer is placed.

### Response:

Example of 1-shot prompt used in MARC-ja (v0.2)
9.5pt13ptPlease classify the product review into either negative or positive sentiment. Please lowercase the output. [footnotecommon1]

Product Review: I like country and initially thought of buying the CD, the movie has a decent story, it's okay

Sentiment:[footnotecommon1] positive

Product Review: I enjoyed it till the end. Personally, I wanted to see more dance scenes. I hope it will be staged.

Sentiment: [footnotecommon1]

Example of 1-shot prompt used in MARC-ja (v0.3) [footnotecommon2]
9.5pt13ptBelow is a combination of instructions explaining the task and contextual inputs. Write a response that adequately meets the request.

### Instructions:

Please classify the following product review into either a positive or negative sentiment class.

### Input:

I like country and initially thought of buying the CD, the movie has a decent story, it's okay

### Response:

### Instructions:

Please classify the following product review into either a positive or negative sentiment class.

### Input:

I enjoyed it till the end. Personally, I wanted to see more dance scenes. I hope it will be staged.

### Response:


$|\phi^{-T}_{\varepsilon}z^{u}-(q_{0}(\nu-T^{\prime}),q_{0}(\nu-T^{\prime}))|=O(\varepsilon)$.
Moreover, when $T\to\infty$, we can also choose $T^{\prime}\to\infty$. We next
choose $T=c\log\varepsilon^{-1}>0$ with small $c$. Then by Gronwall estimate,
we that that
$|\phi^{t}_{\varepsilon}z^{u}-(q_{0}(\nu-t),q_{0}(\nu-t))|=O(\varepsilon^{1-d_{1}})$
for some $0<d_{1}<1$ for all $t\in[-T,0]$. Then we have
$|(q_{0}(\nu-T),q_{0}(\nu-T))-O|<O(\varepsilon^{d_{2}})$ and
$|(q_{0}(\nu-T^{\prime}),q_{0}(\nu-T^{\prime}))-O|<o_{\varepsilon}(1)$ due to
the exponential convergence.

Over the time interval $[-T,0]$, we replace the integral
$\int_{-T}^{0}\\{H_{0},H_{1}\\}(\phi_{\varepsilon}^{t}z^{u}_{\varepsilon},s+t)\,dt$
by $\int_{-T}^{0}\\{H_{0},H_{1}\\}(\gamma(\nu+t),s+t)\,dt$ creating an error
$O(\varepsilon\varepsilon^{1-d_{1}}\log\varepsilon)=o(\varepsilon)$. Moreover,
since $\gamma(t)\to O$ exponentially for both $t\to\pm\infty$, we get
$\int_{-\infty}^{-T}\\{H_{0},H_{1}\\}(\gamma(\nu+t),s+t)\,dt=O(\varepsilon^{d_{2}})$.
We also replace $H_{0}(\phi_{\varepsilon}^{-T}z^{u}_{\varepsilon})$ by
$H_{0}(\gamma(-T^{\prime}+\nu))$ creating an error estimated as
$DH_{0}(\gamma(-T^{\prime}+\nu))|\phi_{\varepsilon}^{-T}z^{u}_{\varepsilon}-\gamma(-T^{\prime}+\nu)|=O(\varepsilon^{1+d_{2}})$.
So we get

$H_{0}(z^{u}_{\varepsilon})-H_{0}(\gamma(-T^{\prime}+\nu))=\varepsilon\int_{-\infty}^{0}\\{H_{0},H_{1}\\}(\gamma(\nu+t),s+t)\,dt+o(\varepsilon).$

Similarly, we get

$H_{0}(\gamma(T^{\prime\prime}+\nu))-H_{0}(z^{s}_{\varepsilon})=\varepsilon\int^{\infty}_{0}\\{H_{0},H_{1}\\}(\gamma(\nu+t),s+t)\,dt+o(\varepsilon).$

Adding the two equations using the fact that $H_{0}$ is a constant along the
orbit $\gamma$, we get

$H_{0}(z^{u}_{\varepsilon})-H_{0}(z^{s}_{\varepsilon})=\varepsilon\int_{\mathbb{R}}\\{H_{0},H_{1}\\}(\gamma(\nu+t),s+t)\,dt+o(\varepsilon).$

In the above integral, we can fix $s=0$ section, then the resulting integral
is the derivative of

$\varepsilon
J(\nu)=\varepsilon\int_{-\infty}^{\infty}H_{1}(\gamma(t+\nu),t)-H_{1}(O,t)\,dt.$

Since we have $\gamma(t)\to O$ exponentially as $t\to\pm\infty$, we get that
the integrals $J(\nu)$ as well as $J^{\prime}(\nu)$ converge absolutely. The
theorem is then proved by setting $\mathcal{M}(\nu)=J^{\prime}(\nu)$. ∎

###  A.2. Smale Horseshoe

It was discovered by Smale that a separatrix splitting gives rise to a
horseshoe. We refer readers to Chapter 5.8 of [BS] and Chapter 6.5 of [KH] for
the definition of a horseshoe and the following theorem.

######  Theorem A.2.

Let $p$ be a hyperbolic fixed point of a diffeomorphism $f:\
U(\subset\mathbb{R}^{n})\to\mathbb{R}^{n}$ and $q$ be a transverse homoclinic
point of $p$. Then for any $\varepsilon>0$, there exists a horseshoe in the
union of the $\varepsilon$-neighborhoods of $p$ and $q$.

The existence of a horseshoe implies the existence of invariant set $\Lambda$
such that $f\Lambda=\Lambda$ and $f$ is conjugate to a two-sided shift in the
space of bi-infinite sequences in the alphabet $\\{0,1,\ldots,n-1\\}$ for some
$n\geq 2$.

###  A.3. The scattering map, proof of Theorem 3.4

###### Proof of Theorem 3.4.

The proof is a generalization of the above proof of Poincaré’s theorem.

Let $H_{0}=H$ be the Schwarzchild Hamiltonian in (3.2) and denote
$H_{\varepsilon}=H_{0}+\varepsilon H_{1}$ be the perturbed Hamiltonian. We
introduce the auxiliary function
$\mathcal{H}_{\varepsilon}=\frac{r^{2}}{L_{z}}(H_{0}+\varepsilon
H_{1}+\frac{1}{2})$. If we use $\mathcal{H}_{\varepsilon}$ as the new
Hamiltonian, then its Hamiltonian flow on the level set
$\mathcal{H}_{\varepsilon}=0$ is a time reparametrization of that of
$H_{\varepsilon}$ on the energy level set $H_{\varepsilon}=-\frac{1}{2}$. We
denote by $\lambda$ the time for the Hamiltonian $\mathcal{H}_{\varepsilon}$,
and by $t$ that of $H_{\varepsilon}$, then we have
$\frac{r^{2}}{L_{z}}d\lambda=dt$ for orbits with $\mathcal{H}_{\varepsilon}=0$
and $H_{\varepsilon}=-1/2$.

We next denote $h_{0}(r,p_{r})=\frac{1}{2}\frac{r^{2}}{L_{z}}(-\alpha
E^{2}+\alpha p_{r}^{2}+r^{-2}L^{2}+1)=\frac{r^{2}}{L_{z}}(H_{0}+\frac{1}{2})$
the Hamiltonian governing the radial motion and
$\mathcal{H}_{\varepsilon}=h_{0}+\varepsilon\mathcal{H}_{1}$ with
$\mathcal{H}_{1}=\frac{r^{2}}{L_{z}}H_{1}$.

Denote by $\Lambda$ the 5 dimensional homoclinic manifold
$\\{(\Gamma(\nu),\Xi_{0}),\ \nu\in\mathbb{R},\ \Xi_{0}\in
T^{*}\mathbb{S}^{2}\\}$ to the unperturbed NHIM $N$. Then we pick a line
$\ell_{\nu,\Xi_{0}}$ normal to $\Lambda$ at the point $(\Gamma(\nu),\Xi_{0})$
and parallel to $Dh_{0}(\Gamma(\nu),\Xi_{0})$. Let $z^{u/s}_{\varepsilon}$ be
the intersection of the stable and unstable manifolds
$W^{u/s}(N_{\varepsilon})$ with $\ell_{\nu,\Xi_{0}}$.

We use $\Phi^{\lambda}_{\varepsilon}$ the flow for the perturbed system
$\mathcal{H}_{\varepsilon}=h_{0}+\varepsilon\mathcal{H}_{1}$ with time
reparametrized by the Mino time. We use the difference
$h_{0}(z^{u}_{\varepsilon})-h_{0}(z^{s}_{\varepsilon})$ as a measurement of
the splitting of the stable and unstable manifolds. We thus have the following
by Newton-Leibniz

$h_{0}(z^{u}_{\varepsilon})-h_{0}(\Phi^{\mu}_{\varepsilon}(z^{u}_{\varepsilon}))=\varepsilon\int_{\mu}^{0}\\{h_{0},\mathcal{H}_{1}\\}(\Phi^{\lambda}_{\varepsilon}(z^{u}))\,d\lambda.$

By the smooth dependence on the base point of the stable and unstable fiber,
we get that $|z^{u/s}_{\varepsilon}-z_{0}|=O(\varepsilon)$ and that for all
$\lambda<0$, the orbit $\Phi^{\lambda}(z^{u})$ on the perturbed unstable fiber
lies within $O(\varepsilon)$ distance of the unperturbed unstable manifold
$\\{(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda)),\ \lambda<0\\}$. In particular,
for each $\mu<0$, there exists $\mu^{\prime}$ such that
$|(\Gamma(\nu+\mu^{\prime}),\Xi(\Xi_{0},\mu^{\prime}))-\Phi^{\mu}(z^{u})|=O(\varepsilon)$,
and we have $\mu^{\prime}\to-\infty$ when $\mu\to-\infty$. Next, by
$\Gamma(\lambda)$’s exponential convergence to $\Gamma_{c}$, we get that
$|\Gamma(\mu)-\Gamma_{c}|=O(\varepsilon^{d_{1}})$ for $\mu=c\log\varepsilon$,
for some $0<d_{1}<1$ by choosing $c>0$ small and
$|\Gamma(\mu^{\prime})-\Gamma_{c}|=o_{\varepsilon}(1)$. Also, by Gronwall
estimate, we get that over the time interval $\lambda\in[c\log\varepsilon,0]$,
we have
$|(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))-\Phi^{\lambda}(z^{u})|=O(\varepsilon^{1-d_{2}})$
for some $0<d_{2}<1$ provided $c$ is small.

We next choose $\mu=c\log\varepsilon$ and replace the integral
$\int_{\mu}^{0}\\{h_{0},\mathcal{H}_{1}\\}(\Phi^{\lambda}_{\varepsilon}(z^{u}))\,d\lambda$
by
$\int_{\mu}^{0}\\{h_{0},\mathcal{H}_{1}\\}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))\,d\lambda$
creating an error $O(\varepsilon^{2-d_{2}}\log\varepsilon)=o(\varepsilon)$.
Next, we get
$\int^{\mu}_{-\infty}\\{h_{0},\mathcal{H}_{1}\\}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))\,d\lambda=O(\varepsilon^{1+d_{1}})$
by the exponential convergence of $\Gamma(\lambda)$ to $\Gamma_{c}$. Moreover,
we replace $h_{0}(\Phi^{\mu}_{\varepsilon}(z^{u}_{\varepsilon}))$ by
$h_{0}(\Gamma(\nu+\mu^{\prime}))$ creating an error estimated as
$|Dh_{0}(\gamma(\mu^{\prime}+\nu))|(|\Phi^{\mu}_{\varepsilon}(z^{u}_{\varepsilon}))-\gamma(\mu^{\prime}+\nu)|)=o(\varepsilon).$

We thus obtain

$h_{0}(z^{u}_{\varepsilon})-h_{0}(\gamma(\mu^{\prime}+\nu))=\varepsilon\int_{-\infty}^{0}\\{h_{0},\mathcal{H}_{1}\\}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))\,d\lambda+o(\varepsilon).$

Similarly, we get

$h_{0}(\gamma(-\mu^{\prime\prime}+\nu))-h_{0}(z^{s}_{\varepsilon})=\varepsilon\int^{\infty}_{0}\\{h_{0},\mathcal{H}_{1}\\}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))\,d\lambda+o(\varepsilon).$

Adding the expressions, we get

$h_{0}(z^{u}_{\varepsilon})-h_{0}(z^{s}_{\varepsilon})=\varepsilon\int_{\mathbb{R}}\\{h_{0},\mathcal{H}_{1}\\}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))\,d\lambda+o(\varepsilon).$

When the integral on the RHS has a nondegenerate zero, then the stable and
unstable manifolds $W^{u/s}(N_{\varepsilon})$ intersect transversally.

We next prove the formula for the scattering map. Let $\tilde{w}$ be an
intersection point of $W^{u}(N_{\varepsilon})$ and $W^{s}(N_{\varepsilon})$
and $\Phi_{\varepsilon}^{\lambda}$ the perturbed flow, then by the theorem of
NHIM, we find points $w^{\pm}\in N_{\varepsilon}$ such that

$|\Phi_{\varepsilon}^{\lambda}(w^{\pm})-\Phi_{\varepsilon}^{\lambda}(\tilde{w})|\to
0,\quad t\to\pm\infty.$

The scattering map thus sends $w^{-}$ to $w^{+}$ by definition.

We have the following equality by Newton-Leibniz

$L_{z}(\tilde{w})-L_{z}(\Phi^{\mu}_{\varepsilon}\tilde{w})=\varepsilon\int_{\mu}^{0}\\{L_{z},H_{1}\\}\frac{dt}{d\lambda}(\Phi^{\lambda}_{\varepsilon}\tilde{w})\,d\lambda,$
$L_{z}(w^{-})-L_{z}(\Phi^{\mu}_{\varepsilon}w^{-})=\varepsilon\int_{\mu}^{0}\\{L_{z},H_{1}\\}\frac{dt}{d\lambda}(\Phi^{\lambda}_{\varepsilon}w^{-})\,d\lambda.$

Using the same argument as above, we replace the integrals on the RHS by
integrals along the unperturbed flows
$(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))$ and
$(\Gamma_{c}(\nu+\lambda),\Xi(\Xi_{0},\lambda))$ respectively. To approximate
$\Phi^{\lambda}_{\varepsilon}w^{-}$ by
$(\Gamma_{c}(\nu+\lambda),\Xi(\Xi_{0},\lambda))$, we apply Gronwall over the
time interval $[\mu,0]$ where $\mu=c\log\varepsilon$ to get the estimate of
the error $\varepsilon^{1-d_{2}}$ for some $0<d_{2}<1$ if $c>0$ is chosen
sufficiently small.

Since we have
$|\Phi^{\mu}_{\varepsilon}w^{-}-\Phi^{\mu}_{\varepsilon}\tilde{w}|\to 0$
exponentially, we get by taking difference

$L_{z}(\tilde{w})-L_{z}(w^{-})=\varepsilon\int_{-\infty}^{0}\left[\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))-\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma_{c},\Xi(\Xi_{0},\lambda))\right]\,d\lambda+o(\varepsilon),$

Similarly, we get

$L_{z}(w^{+})-L_{z}(\tilde{w})=\varepsilon\int^{\infty}_{0}\left[\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))-\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma_{c},\Xi(\Xi_{0},\lambda))\right]\,d\lambda+o(\varepsilon).$

Adding up the last two equations, we get

$L_{z}(w^{+})-L_{z}(w^{-})=\varepsilon\int_{\mathbb{R}}\left[\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma(\nu+\lambda),\Xi(\Xi_{0},\lambda))-\partial_{\varphi}H_{1}\frac{dt}{d\lambda}(\Gamma_{c},\Xi(\Xi_{0},\lambda))\right]\,d\lambda+o(\varepsilon).$

This completes the proof. ∎

######  Remark A.3.

  1. (1)

We do not have an expression for the scattering map in the
$(\theta,p_{\theta})$-components, since $p_{\theta}$ is not a conserved
quantity for the unperturbed system. If we introduce action-angle coordinates
$(\alpha_{\theta},J_{\theta})$ in the $(\theta,p_{\theta})$ components, then
we have similar expression for the scattering map.

  2. (2)

The proof of Theorem 5.3 is completely analogous. If the Kerr Hamiltonian is
perturbed to $H=H_{0}+\varepsilon H_{1}$. We introduce (see (5.6))

(A.1) $\mathcal{H}_{\varepsilon}=H_{r}+H_{\theta}+\Sigma+2\varepsilon\Sigma
H_{1}=\Delta p_{r}^{2}-\frac{R}{\Delta}+Q+2\varepsilon\Sigma H_{1}.$

Then we choose $h_{0}=\Delta p_{r}^{2}-\frac{R}{\Delta}+Q$ and
$\mathcal{H}_{1}=2\Sigma H_{1}$ in the above proof, then the proof goes
through for the Kerr case.

##  Appendix B The theorem of normally hyperbolic invariant manifolds

In this section we give the version of normally hyperbolic invariant manifold
theorem that we used in the proof of our main theorem. The standard references
are [HPS, F].

######  Definition B.1 (NHIM).

Let $N\subset M$ be a submanifold $($maybe noncompact$)$ invariant under $f$,
$f(N)=N$. We say that $N$ is a normally hyperbolic invariant manifold if there
exist a constant $C>0$, rates $0<\lambda<\mu^{-1}<1$ and an invariant $($under
$Df)$ splitting for every $x\in N$

$T_{x}M=E^{s}(x)\oplus E^{u}(x)\oplus T_{x}N$

in such a way that

$\displaystyle v\in E^{s}(x)$
$\displaystyle\Leftrightarrow\quad|Df^{n}(x)v|\leq C\lambda^{n}|v|,\quad n\geq
0,$ $\displaystyle v\in E^{u}(x)$
$\displaystyle\Leftrightarrow\quad|Df^{n}(x)v|\leq C\lambda^{|n|}|v|,\ \ n\leq
0,$ $\displaystyle v\in T_{x}N$
$\displaystyle\Leftrightarrow\quad|Df^{n}(x)v|\leq C\mu^{n}|v|,\quad
n\in\mathbb{Z}.$

Here the Riemannian metric $|\cdot|$ can be any prescribed one, which may
change the constant $C$ but not $\lambda,\mu$.

######  Theorem B.2.

Suppose $N$ is a NHIM under the $C^{r}$, $r>1$, diffeomorphism $f:\ M\to M$.
Denote $\ell=\min\\{r,\frac{|\ln\lambda|}{|\ln\mu|}\\}$. Then for any $C^{r}$
$f_{\epsilon}$ that is sufficiently close to $f$ in the $C^{1}$ norm,

  1. (1)

there exists a NHIM $N_{\epsilon}$ that is a $C^{\ell}$ graph over $N$,

  2. (2)

$($Invariant splitting$)$ There exists a splitting for $x\in N_{\epsilon}$

$T_{x}M=E^{u}_{\epsilon}(x)\oplus E^{s}_{\epsilon}(x)\oplus T_{x}N_{\epsilon}$

invariant under the map $f_{\epsilon}$. The bundle $E^{u,s}_{\epsilon}(x)$ is
$C^{\ell-1}$ in $x$.

  3. (3)

There exist $C^{\ell}$ stable and unstable manifolds $W^{s}(N_{\epsilon})$ and
$W^{u}(N_{\epsilon})$ that are invariant under $f$ and are tangent to
$E_{\epsilon}^{s}\oplus TN_{\epsilon}$ and $E_{\epsilon}^{u}\oplus
TN_{\epsilon}$ respectively.

  4. (4)

The stable and unstable manifolds $W^{u,s}(N_{\epsilon})$ are fibered by the
corresponding stable and unstable leaves $W^{u,s}_{x,\epsilon}:=\\{y\
|d(f_{\varepsilon}^{n}(y),f_{\varepsilon}^{n}(x))\to 0,n\to+\infty\
\mathrm{for}\ s,n\to-\infty\ \mathrm{for}\ s\\}$:

$W^{u}(N_{\epsilon})=\cup_{x\in N_{\epsilon}}W_{x,\epsilon}^{u},\quad
W^{s}(N_{\epsilon})=\cup_{x\in N_{\epsilon}}W_{x,\epsilon}^{s}.$

  5. (5)

The maps $x\mapsto W_{x,\epsilon}^{u,s}$ are $C^{\ell-j}$ when
$W_{x,\epsilon}^{u,s}$ is given $C^{j}$ topology.

  6. (6)

$($[DLS08]$)$If $f$ and $f_{\epsilon}$ are Hamiltonian, then $N_{\epsilon}$ is
symplectic and the map $f_{\epsilon}$ restricted to $N_{\epsilon}$ is also
Hamiltonian.

##  Appendix C Perturbing the Schwarzschild metric

In this section, we verify the nondegeneracy condition in the above Theorem
3.5 and 4.2 for the perturbed Schwarzschild metric which satisfies the
linearized Einstein field equation in the vacuum.

###  C.1. Regge-Wheeler equation

We first summarize the result from [RW]. Suppose the background metric
$g_{\mu\nu}$ is perturbed by $h_{\mu\nu}$. Then the perturbed Ricci curvature
has the form $R_{\mu\nu}+\delta R_{\mu\nu}$. The vacuum Einstein equation
requires that $\delta
R_{\mu\nu}=-\delta\Gamma^{\beta}_{\mu\nu;\beta}+\delta\Gamma^{\beta}_{\mu\beta;\nu}=0,$
where “;” means the covariant derivative and the linearized Christoffel symbol
has the form

$\delta\Gamma^{\beta}_{\mu\nu}=\dfrac{1}{2}g^{\alpha\nu}(h_{\beta\nu;\gamma}+h_{\gamma\nu;\beta}-h_{\beta\gamma;\nu}).$

So the equation $\delta R_{\mu\nu}=0$ is linear in $h$.

We then expand $h$ into Fourier series in terms of spherical harmonic
functions

$h_{\mu\nu}=\sum\tilde{h}_{\mu\nu,\ell}^{m}(T,r)Y_{\ell}^{m}(\theta,\phi).$

Here $Y_{\ell}^{m}$ is the spherical harmonic function defined as

$Y_{\ell}^{m}(\theta,\phi)=\sqrt{\frac{2\ell+1}{4\pi}\frac{(\ell-m)!}{(\ell+m)!}}P_{\ell}^{m}(\cos\theta)e^{im\phi}$

and $P_{\ell}^{m}$ is the associated Legendre polynomial

$P_{\ell}^{m}(x)=(-1)^{m}(1-x^{2})^{m/2}\frac{d^{m}}{dx^{m}}P_{\ell}(x)=\frac{(-1)^{m}}{2^{\ell}\ell!}(1-x^{2})^{m/2}\frac{d^{\ell+m}}{dx^{\ell+m}}(x^{2}-1)^{\ell}$

where $P_{\ell}$ is the unassociated Legendre polynomial. We list a few to be
used later

(C.1) $\displaystyle P_{0}$ $\displaystyle=1,\quad P_{1}=x,\quad
P_{2}=\frac{1}{2}(3x^{2}-1),$ $\displaystyle P_{n}^{0}$
$\displaystyle=P_{n},\quad P_{1}^{1}=(1-x^{2})^{1/2},$ $\displaystyle
P_{2}^{1}$ $\displaystyle=-3x(1-x^{2})^{1/2},\quad P_{2}^{2}=3(1-x^{2}).$

The linearity of the equation allows us to consider only each individual
Fourier mode $k,\ell$. Moreover, we also assume that the $t$-dependence is
quantized, i.e. $h$ is periodic with respect to $t$ with frequency
$\omega=kc$, $\omega t=kT$. Then we further define

$\tilde{h}_{\mu\nu,\ell}^{m}(T,r)=\sum_{k}\hat{h}_{\mu\nu,\ell}^{m}(r)e^{ikT}.$

There are two cases: the odd parity and even parity cases.

After modulo a gauge transformation, the case of odd parity has the general
form

$h_{\mu\nu}=\left[\begin{array}[]{cccc}0&0&-h_{0}\frac{1}{\sin\theta}\partial_{\varphi}Y_{\ell}^{m}&h_{0}\sin\theta\partial_{\theta}Y_{\ell}^{m}\\\
0&0&-h_{1}\frac{1}{\sin\theta}\partial_{\varphi}Y_{\ell}^{m}&h_{1}\sin\theta\partial_{\theta}Y_{\ell}^{m}\\\
&*&0&0\\\ &*&0&0\end{array}\right],$

where $h_{0}=h_{0}(\tau,r)$ and $h_{1}=h_{1}(\tau,r)$ are periodic in $\tau$.
In both the odd and even parity cases, the radial functions are independent of
$m=-\ell,-(\ell-1),\ldots,\ell-1,\ell$, for each given $\omega$ and
$\ell=0,1\ldots$. Moreover, there are equations that should be satisfied by
the radial functions.

$Q(r)=\frac{1}{r}\alpha h_{1}(r),\quad\alpha^{-1}kh_{0}+\frac{d}{dr}(rQ)=0.$

Then $Q$ satisfies the equation called Regge-Wheeler equation
$\frac{d^{2}Q}{(dr^{*})^{2}}+k_{\mathrm{eff}}^{2}(r)Q=0,$ where
$r^{*}=r+2M(\ln(\frac{r}{2M}-1))$ and

$k_{\mathrm{eff}}^{2}=k^{2}-L(L+1)\frac{\alpha}{r^{2}}+6M\alpha\frac{1}{r^{3}}=k^{2}+\frac{1}{r^{2}}\alpha\left(-L(L+1)+\frac{6M}{r}\right).$

We next consider the case of even parity. The general even parity perturbation
has the form after the gauge transformation

$h_{\mu\nu}=\left[\begin{array}[]{cccc}\alpha
HY_{\ell}^{m}&H_{1}Y_{\ell}^{m}&0&0\\\
H_{1}Y_{\ell}^{m}&\alpha^{-1}HY_{\ell}^{m}&0&0\\\ 0&0&r^{2}KY_{\ell}^{m}&0\\\
0&0&0&r^{2}K\sin^{2}\theta Y_{\ell}^{m}\end{array}\right]$

where $H,H_{1},K$ are functions of $\tau$ and $r$ and the dependence on $\tau$
is $1$-periodic. Moreover, if we consider only the stationary case $k=0$, then
$H_{1}=0$.

The functions $K$ and $H$ solve the equations

$\begin{cases}&(K+H)^{\prime}+\frac{2M}{r^{2}}\alpha^{-1}H=0,\\\
&H^{\prime}+\frac{2M}{r^{2}}\alpha^{-1}H+\frac{2H}{r}+\frac{1}{2M}(L-1)(L+2)(K+H)=0.\end{cases}$

The solution for $\ell=0$ is trivial. For $\ell=1$, the solution is given
explicitly as

(C.2) $H=-\frac{2M}{r^{2}\alpha},\quad
K=\frac{1}{M}\left(\frac{2M}{r}+\ln(1-\frac{2M}{r})\right).$

For $\ell>1$, we eliminate $K+H$ to obtain an equation for $A=r(r-2M)H$

$A^{\prime\prime}-\left(\frac{1}{r}+\frac{1}{r-2M}\right)A^{\prime}-(\ell-1)(\ell+2)\frac{A}{r(r-2M)}=0.$

The general solution can be written as

$A(r)=aP_{\ell}^{(2)}(1-\frac{r}{M})+bQ_{\ell}^{(2)}(1-\frac{r}{M}),\quad
a,b\in\mathbb{R},$

where $P_{\ell}^{(2)},\ Q_{\ell}^{(2)}$ are associated Legendre polynomials of
the first and second kinds respectively.

We take $a=M/3,b=0,$ and $\ell=2$ to yield the solution

(C.3) $H(r)=\frac{1-(1-r/M)^{2}}{r(r-2M)}M=-\frac{1}{M},\quad
K(r)=\frac{1}{M}+\frac{1}{2r}+\frac{1}{2(r-2M)}$

with $Y_{2}^{2}=\frac{3}{4}\sqrt{\frac{5}{6\pi}}\sin^{2}\theta e^{2i\varphi}$.

###  C.2. Checking the Melnikov condition for Arnold diffusion

In this section, we verify the nonvanishing condition of the Melnikov function
for the above constructed perturbations. Suppose the perturbed metric is

$\tilde{g}_{\mu\nu}=g_{\mu\nu}+\varepsilon
h_{\mu\nu}=\alpha(-1+\varepsilon\tilde{H})d\tau^{2}+\alpha^{-1}(1+\varepsilon\tilde{H})dr^{2}+r^{2}(1+\varepsilon\tilde{K})(d\theta^{2}+\sin^{2}\theta
d\varphi^{2}).$

We treat $\frac{1}{2}\tilde{g}_{\mu\nu}$ as the perturbed Lagrangian
$L_{\varepsilon}$. Performing a formal Legendre transform We obtain the
perturbed Hamiltonian

$\displaystyle 2H_{\varepsilon}$
$\displaystyle=\alpha^{-1}(-1+\varepsilon\tilde{H})^{-1}p_{\tau}^{2}+\alpha(1+\varepsilon\tilde{H})^{-1}p_{r}^{2}+r^{-2}(1+\varepsilon\tilde{K})^{-1}(p_{\theta}^{2}+\sin^{-2}\theta
p_{\varphi}^{2})$
$\displaystyle=2H_{0}-\varepsilon\left(\alpha^{-1}\tilde{H}p_{\tau}^{2}+\alpha\tilde{H}p_{r}^{2}+r^{-2}\tilde{K}(p_{\theta}^{2}+\sin^{-2}\theta
p_{\varphi}^{2})\right)+O(\varepsilon^{2})$
$\displaystyle:=2H_{0}+2\varepsilon H_{1}+O(\varepsilon^{2}).$

Next, we show that an explicit perturbation satisfies the assumption of
Theorem 3.5.

###### Checking the assumption of Theorem 3.5.

We choose $H,K$ as in (C.3) and denote $\tilde{H}=HY_{2}^{2},\
\tilde{K}=KY_{2}^{2}.$ We have

$H_{1}=e^{2i\varphi}\sin^{2}\theta\left(-\alpha^{-1}\frac{E^{2}}{M}-\alpha\frac{p_{r}^{2}}{M}+r^{-2}KL^{2}\right).$

By the total energy conservation along the homoclinic orbit in the unperturbed
system, we have

$-1=2H=-\alpha^{-1}E^{2}+\alpha
p_{r}^{2}+r^{-2}L^{2},\quad-1=-\alpha^{-1}(r_{-})E^{2}+r_{-}^{-2}L^{2}.$

Thus we simplify the expression of $H_{1}$ as follows by eliminating $p_{r}$

$H_{1}=e^{2i\varphi}\sin^{2}\theta\left(\frac{1}{M}-2\frac{E^{2}}{\alpha
M}+r^{-2}(K+\frac{1}{M})L^{2}\right).$

We get the Melnikov potential from (3.9)

(C.4) $\displaystyle J(\nu)$
$\displaystyle=\frac{1}{L}\int_{\mathbb{R}}\sin^{2}\theta(\lambda-\nu)e^{2i(\varphi(0)+\frac{\lambda-\nu}{L^{2}})}\left(-\frac{2E^{2}}{M}\left(\frac{r(\lambda)^{2}}{\alpha(r(\lambda))}-\frac{r_{-}^{2}}{\alpha(r_{-})}\right)\right.$
$\displaystyle\left.+\frac{1}{M}\left(r(\lambda)^{2}-r_{-}^{2}\right)+L^{2}\left(\frac{1}{r(\lambda)}+\frac{1}{r(\lambda)-2M}-\frac{1}{r_{-}}-\frac{1}{r_{-}-2M}\right)\right)\,d\lambda.$

where $\sin^{2}\theta$ can be expressed using (3.8) and $r=\frac{1}{u}$ using
(3.7). We rewrite the above $J(\nu)$ as

$J(\nu)=\frac{1}{L}\int_{\mathbb{R}}\left(1-\left(\cos\theta(0)+\frac{\sqrt{b^{2}-1}}{b}\sin(b(\lambda-\nu))\right)^{2}\right)e^{2i(\varphi(0)+\frac{\lambda-\nu}{L^{2}})}Q(r(\lambda))\,d\lambda,$

where we use $Q(r(\lambda))$ to denote the $r$-dependent term in the integrand
of (C.4). When we complexify $\lambda$, the only poles of the integrand are
poles of $r(\lambda),r(\lambda)^{-1}$ and $(r(\lambda)-2M)^{-1}$ where

$r(\lambda)=\left(u_{1}-a^{2}\mathrm{sech}^{2}(\frac{a\lambda}{2})\right)^{-1},\
\lambda\in\mathbb{C}.$

We introduce our initial contour of integration as $C=C_{-}\cup C_{+}$ where
$C_{+}=\\{\mathrm{Im}z=\frac{i\pi}{a}\\}$ oriented from left to right and
$C_{-}=\\{\mathrm{Im}z=-\frac{i\pi}{a}\\}$ oriented from right to left. To
simplify the calculation, we consider first the extremal case $b^{2}\to 1$ so
that $\sin^{2}\theta(\lambda-\nu)\to\sin^{2}\theta(0)$ and
$\theta(0)\to\pi/2$. Then, we obtain the following contour integral

$J(\nu)=\frac{1}{L}e^{2i(\varphi(0)-\frac{\nu}{L^{2}})}\frac{-2}{\sinh\frac{2\pi}{aL^{2}}}\oint_{C}e^{2i\frac{z}{L^{2}}}Q(r(z))\,dz.$

We note that the general $b^{2}\neq 1$ case can be done similarly as follows
with a more complicated factor in front of the contour integral.

We next evaluate the contour integral. To simplify the discussion, we
normalize $M=1$ and also use an observation of [Mo] by examining $a\to 0$ (we
remark that the general $a\neq 0$ can be done directly with some more labors).
This means the roots $u_{2}<u_{1}$ of the RHS of the
$\frac{du}{d\lambda}$-equation in (3.6) nearly coincide (we have
$a^{2}=u_{1}-u_{2}$). This means that $L^{2}$ is close to $L^{2}_{isco}=12$,
$E^{2}$ is close to $E_{isco}^{2}=\frac{8}{9}$ and $u_{1}$ is close to $1/3$.
Setting $z=\lambda-\frac{i\pi}{a}$, then we get

$u(z)=u_{1}+a^{2}\frac{1}{\sinh^{2}(az/2)}\to\frac{1}{3}+\frac{4}{z^{2}}=\frac{z^{2}+12}{3z^{2}},\quad\mathrm{as}\
a\to 0.$

$Q(r)$ is a linear combination of terms $1,r^{2},\frac{r^{3}}{r-2},r^{-1}$ and
$\frac{1}{r-2}$. Note that $1,r^{2},r^{-1}$ and $r^{3}$ do not contribute to
the residue and we have in the limit $a\to 0$ that
$\frac{1}{r-2}=\frac{z^{2}+12}{z^{2}-24}$ has residue $\pm\frac{9}{\sqrt{6}}$
at $z=\pm\sqrt{24}$ and
$\frac{r^{3}}{r-2}=\frac{27z^{6}}{(z^{2}+12)^{2}}\frac{1}{z^{2}-24}$ has
residue $\pm 9\sqrt{6}$ at $z=\pm\sqrt{24}$.

We then deform the contour $C$ to another bounded closed curve $\tilde{C}$
enclosing the poles. Since $u$ and the poles depend on $a$ continuously, for
small $a\neq 0$, the poles are still enclosed by $\tilde{C}$ and the residues
also depends on $a$ continuously. Our goal is then to show that the contour
integral $\frac{1}{2\pi i}\oint_{\tilde{C}}e^{2i\frac{z}{L^{2}}}Q(r(z))\,dz$
is nonvanishing for $a=0$. Indeed after some calculations (substituting $Q(r)$
with $M=1,E^{2}=\frac{8}{9},L^{2}=12$), we have that sum of the residues is

$e^{4i\frac{\sqrt{6}}{12}}(2\sqrt{6})-e^{-4i\frac{\sqrt{6}}{12}}(2\sqrt{6})\neq
0.$

This completes the proof. ∎

###  C.3. Checking the Melnikov condition for oscillatory motion

In this section, we show that an explicit perturbation satisfies the
assumption of Theorem 4.2.

###### Checking the assumption of Theorem 4.2.

We choose $H,K$ as in (C.2) and denote $\tilde{H}=HY_{1}^{1},\
\tilde{K}=KY_{1}^{1}$ where $Y^{1}_{1}=\sin\theta e^{i\varphi}$ up to a scalar
multiple. We next show that the perturbation chosen in this way satisfies the
assumptions of Theorem 4.2.

We first verify assumption (1). This follows immediately from the expressions
of $\tilde{H}$ and $\tilde{K}$. We next verify assumption (2). From the
equations

$\dot{\theta}=\frac{\partial H_{\varepsilon}}{\partial
p_{\theta}}=r^{-2}(1+\varepsilon\tilde{K})^{-1}p_{\theta},\quad\dot{p}_{\theta}=-\frac{\partial
H_{\varepsilon}}{\partial\theta},$

we see that $\theta=\pi/2,p_{\theta}=0$ is a solution. Indeed, we have
$\dot{p}_{\theta}=0$ if $\theta=\pi/2$ since $H_{\varepsilon}$ depends on
$\theta$ through $\sin\theta$ only so the $\frac{\partial
H_{\varepsilon}}{\partial\theta}$ has a factor $\cos\theta$ which vanishes
when $\theta=\pi/2$. On the other hand when $p_{\theta}=0$ we also have
$\dot{\theta}=0$. We next work on assumption (3). For this purpose we write
down the expression for the perturbing Hamiltonian function $H_{1}$ first
(using energy conservation as along the unperturbed homoclinic orbit to
infinity)

$H_{1}=e^{i\varphi}(-H+2\alpha^{-1}HE^{2}+r^{-2}(K-H)L^{2}).$

Since we have the expression of the homoclinic orbit parametrized by $\lambda$
and $d\lambda=\frac{L}{r^{2}}dt$. We also have $r(t)\sim|t|^{2/3}$, which
shows that $\lambda$ is actually defined on a bounded time interval $(a,b)$ to
be determined more precicely below. Then recalling that
$\lim_{r\to\infty}r^{2}(-H+2\alpha^{-1}HE^{2})=-2M(1-2E^{2})$, we get the
Melnikov potential

$J(\nu)=\frac{1}{L}\int_{a}^{b}e^{i(\varphi_{0}+\frac{\lambda-\nu}{L^{2}})}\left(r^{2}(-H(r)+2\alpha^{-1}H(r)E^{2})+2M(1-2E^{2})+(K(r)-H(r))L^{2})\right)\,d\lambda$

where $r$ is a function of $\lambda$.

To evaluate the function, we next work out $r(\lambda)$ in the range of large
$L^{2}$. Then using the definitions in Section 4.2.1, we find that
$u_{1}u_{2}=\frac{2}{\ell}(\frac{1}{2M}-\frac{2}{\ell})=\frac{1}{L^{2}}$ is
small. Then $\mu=\frac{M}{\ell}$ and $k=\frac{4\mu}{1-4\mu}$ are also small.
For sufficiently small $k$, the elliptic integrals can be approximated as
follows

$\displaystyle F(\varphi,k)$
$\displaystyle=\int_{0}^{\varphi}\frac{d\theta}{\sqrt{1-k^{2}\sin^{2}\theta}}=\int_{0}^{\varphi}(1+\frac{k^{2}}{2}\sin^{2}\theta+O(k^{4}))\,d\theta$
$\displaystyle=(1+\frac{k^{2}}{2})\varphi-\frac{k^{2}}{4}\sin
2\varphi+O(k^{4}),$ $\displaystyle K(k)$
$\displaystyle=(1+\frac{k^{2}}{2})\frac{\pi}{2}+O(k^{4}).$
$\displaystyle\lambda(\chi)$
$\displaystyle=\frac{2}{1-4\mu}\left[\frac{1}{2}(1+\frac{k^{2}}{2})\chi-\frac{k^{2}}{4}\sin\chi+O(k^{4})\right].$

We can then find $\chi$ as a function of $\lambda$ as

$\chi=c\lambda+\frac{k^{2}}{2+k^{2}}\sin(c\lambda)+O(k^{4}),$

where $c=\frac{1-4\mu}{1+\frac{k^{2}}{2}}=1-4\mu+O(\mu^{2})$ and the domain
for $\lambda$ is $[a,b]=c^{-1}[-\pi+O(k^{4}),\pi+O(k^{4})]$ whose endpoints
correspond to $\chi=\pm\pi$ where $u=0$. Then we get

$r(\lambda)=\frac{1}{u}=\frac{\ell}{1+\cos\chi}=\frac{\ell}{1+\cos\chi}=\frac{\ell}{1+\cos(c\lambda)-\frac{k^{2}}{2+k^{2}}\sin^{2}(c\lambda)+O(k^{4})}.$

In (C.2), we have the expansion for large $\ell$ and large $r$

$\displaystyle K$ $\displaystyle=-\frac{8M}{r^{2}}+O(r^{-3})$ $\displaystyle
r^{2}(-H(r)+2\alpha^{-1}H(r)E^{2})$
$\displaystyle=-2M(1-2E^{2})-4M^{2}(1-2E^{2})^{2}/r+O(r^{-2}).$

Now the integral becomes (using $\ell^{-1}=O(L^{-2})=O(k)$)

$\displaystyle J(\nu)$
$\displaystyle=\frac{-4M^{2}(1-2E^{2})^{2}}{L}e^{i(\varphi_{0}+\frac{-\nu}{L^{2}})}\int_{a}^{b}e^{i\frac{\lambda}{L^{2}}}\left(\frac{1}{r}+O(r^{-2})\right)\,d\lambda$
$\displaystyle=\frac{-4M^{2}(1-2E^{2})^{2}}{L}e^{i(\varphi_{0}+\frac{-\nu}{L^{2}})}\frac{1}{\ell}\int_{a}^{b}e^{i\frac{\lambda}{L^{2}}}\left(1+\cos(c\lambda)\right)\,d\lambda+O(L^{-5}).$

Letting $L\to\infty$, the integral becomes
$\int_{-\pi}^{\pi}(1+\cos\lambda)\,d\lambda=2\pi$, so for large $L$, it is
clear that the integral does not vanish. ∎

## Acknowledgment

The author would like to express his deep gratitudes to Professor S.-T. Yau
for suggesting the topic. He also would like to thank Mr. Yifan Guo for
drawing all the figures. The author is supported by NSFC (Significant project
No.11790273) in China and Beijing Natural Science Foundation (Z180003).

## References

  * [1]
  * [A64] Arnol’d, V.I. Instability of dynamical systems with several degrees of freedom(Instability of motions of dynamic system with five-dimensional phase space). Soviet Mathematics 5 (1964): 581-585.
  * [A66] Arnol’d, V.I. The stability problem and ergodic properties for classical dynamical systems. Proceedings of International Congress of Mathematicians, Moscow (1966) 5-11, in V. I. Arnold-Collected Works. Springer Berlin Heidelberg (2014) 107-113.
  * [A94] Arnol’d, V.I. Mathematical problems in classical physics. Trends and perspectives in applied mathematics, 1-20, Appl. Math. Sci., 100, Springer, New York, 1994.
  * [A05] Arnol’d, V.I. Arnold’s problems, Springer, New York, 2005.
  * [A89] Arnol’d, V.I., Mathematical methods of classical mechanics. Vol. 60. Springer Science & Business Media, 1989.
  * [AKN] Arnold, Vladimir I., Valery V. Kozlov, and Anatoly I. Neishtadt. Mathematical aspects of classical and celestial mechanics. Vol. 3. Springer Science & Business Media, 2007.
  * [BS] Brin, Stuck, Introduction to dynamical systems, CUP, 2003.
  * [Bo] Bombelli, Luca. Particle motion around perturbed black holes: The onset of chaos. Deterministic Chaos in General Relativity. Springer US, 1994. 145-154.
  * [BGH] Brink, Jeandrew, Marisa Geyer, and Tanja Hinderer. The Astrophysics of Resonant Orbits in the Kerr Metric. arXiv preprint arXiv:1501.07728 (2015).
  * [C] Chandrasekhar, Subrahmanyan. The mathematical theory of black holes. Research supported by NSF. Oxford/New York, Clarendon Press/Oxford University Press (International Series of Monographs on Physics. Volume 69), 1983, 663 p. 1 (1983).
  * [CK] Demetrios Christodoulou and Sergiu Klainerman. The global nonlinear stability of the Minkowski space, volume 41 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993
  * [CX] Cheng, Chong-Qing, and Jinxin Xue. Arnold diffusion in nearly integrable Hamiltonian systems of arbitrary degrees of freedom. arXiv preprint arXiv:1503.04153 (2015).
  * [CY1] Cheng C.-Q. & Yan J., Existence of diffusion orbits in a priori unstable Hamiltonian systems, J. Differential Geometry, 67 (2004) 457-517.
  * [CY2] Cheng C.-Q. & Yan J., Arnold diffusion in Hamiltonian Systems: a priori Unstable Case, J. Differential Geometry, 82 (2009) 229-277.
  * [DKN] Efthimia Deligianni, Jutta Kunz, Petya Nedkova, Quasi-periodic oscillations from the accretion disk around distorted black holes, Arxiv: 2003.01252.
  * [DKRS] A. Delshams, V. Kaloshin, A. de la Rosa, T. M. Seara, Global Instability in the Restricted Planar Elliptic Three Body Problem, Commun. Math. Phys. 366, pages1173-1228(2019).
  * [DLS06] Delshams A. de la Llave R. & Seara T.M. A geometric mechanism for diffusion in Hamiltonian systems overcoming the large gap problem: heuristics and rigorous verification on a model. Mem. Amer. Math. Soc 179 (2006): 844
  * [DLS08] Delshams A. de la Llave R. & Seara T.M. Geometric properties of the scattering map of a normally hyperbolic invariant manifold. Advances in Mathematics 217.3 (2008): 1096-1153.
  * [F] Fenichel N., Persistence and smoothness of invariant manifolds for flows, Indiana Univ. Math. J 21 (1971) 193-226.
  * [GAC] Lukes-Gerakopoulos, Georgios, Theocharis A. Apostolatos, and George Contopoulos. Observable signature of a background deviating from the Kerr metric. Physical Review D 81.12 (2010): 124005.
  * [GHW] Gralla, Samuel E., Daniel E. Holz, and Robert M. Wald. Black hole shadows, photon shells, and lensing rings. Physical Review D 100.2 (2019): 024018.
  * [GK] Glampedakis, Kostas, and Daniel Kennefick. Zoom and whirl: Eccentric equatorial orbits around spinning black holes and their evolution under gravitational radiation reaction. Physical Review D 66.4 (2002): 044002. (2002).
  * [GKS] Elena Giorgi, S. Klainerman, J. Szeftel, A general formalism for the stability of Kerr, Arxiv: 2002.02740.
  * [GL] Gralla, Samuel E., and Alexandru Lupsasca. Null geodesics of the Kerr exterior. Physical Review D 101.4 (2020): 044032.
  * [GLS] Gidea, Marian, Rafael de la Llave, and Tere M-Seara. A general mechanism of diffusion in Hamiltonian systems: Qualitative results. Communications on Pure and Applied Mathematics 73.1 (2020): 150-209.
  * [GLP] Grossman, Rebecca, Janna Levin, and Gabe Perez-Giz. Harmonic structure of generic Kerr orbits. Physical Review D 85.2 (2012): 023012
  * [GMS] Guardia, Marcel, Pau Martín, and Tere M. Seara. Oscillatory motions for the restricted planar circular three body problem. Inventiones mathematicae 203.2 (2016): 417-492.
  * [HF] Hinderer, Tanja, and Eanna E. Flanagan. Two-timescale analysis of extreme mass ratio inspirals in Kerr spacetime: Orbital motion. Physical Review D 78.6 (2008): 064028.
  * [HLS] James Healy, Janna Levin, and Deirdre Shoemaker, Zoom-Whirl Orbits in Black Hole Binaries, arXiv:0907.0671v2 [gr-qc] 23 Sep 2009
  * [HPS] Hirsch M. Pugh C. & Shub M., Invariant Manifolds, Lecture Notes Math. 583 (1977) Springer-Verlag.
  * [J] Michael D. Johnson, Alexandru Lupsasca, Andrew Strominger, et al, Universal interferometric signatures of a black hole’s photon shell. arXiv:1907.04329v2 [astro-ph.IM] 27 Mar 2020
  * [KC] Kao, J-K., and H. T. Cho. The onset of chaotic motion of a spinning particle around the Schwarzchild black hole. Physics Letters A 336.2 (2005): 159-166.
  * [KH] Katok, Hasselblatt, Introduction to the modern theory of dynamical systems, CUP.
  * [KS] S. Klainerman, J. Szeftel, Global nonlinear stability of Schwarzschild spacetime under polarized perturbations, arXiv:1711.07597.
  * [LP1] Levin, Janna, and Gabe Perez-Giz. Homoclinic orbits around spinning black holes. I. Exact solution for the Kerr separatrix. Physical Review D 79.12 (2009): 124013.
  * [LP2] Perez-Giz, Gabe, and Janna Levin. Homoclinic orbits around spinning black holes. II. The phase space portrait. Physical Review D 79.12 (2009): 124014.
  * [LS] Llibre, J., Simó, C.: Oscillatory solutions in the planar restricted three-body problem. Math. Ann. 248(2), 153-184 (1980)
  * [M] Moser, Jurgen. Stable and random motions in dynamical systems: With special emphasis on celestial mechanics. Vol. 1. Princeton university press, 2001.
  * [M87] Wielgus, M, et al, Monitoring the Morphology of M87* in 2009-2017 with the Event Horizon Telescope, Astrophysics Journal, vol 901, no 67, 2020.
  * [Mc] McGehee, R., A stable manifold theorem for degenerate fixed points with applications to celestial mechanics. J. Differ. Equ. 14, 70-88 (1973)
  * [Mo] Moeckel, Richard. A nonintegrable model in general relativity. Communications in mathematical physics 150.2 (1992): 415-430.
  * [N] New York Times, Infinite Visions Were Hiding in the First Black Hole Image’s Rings, https://www.nytimes.com/2020/03/28/science/black-hole-rings.html.
  * [P] Pöschel, Jürgen. A lecture on the classical KAM theorem. arXiv preprint arXiv:0908.2234 (2009).
  * [RW] Regge, Tullio, and John A. Wheeler. Stability of a Schwarzschild singularity. Physical Review 108.4 (1957): 1063.
  * [SS] O. Semerák , P. Suková, Free motion around black holes with discs or rings: between integrability and chaos, Monthly Notices of the Royal Astronomical Society, Volume 404, Issue 2, May 2010, Pages 545-574
  * [T] Teo, Edward. Spherical photon orbits around a Kerr black hole. General Relativity and Gravitation 35.11 (2003): 1909-1926.
  * [Te] Teukolsky, Saul A. Perturbations of a rotating black hole. I. Fundamental equations for gravitational, electromagnetic, and neutrino-field perturbations. The Astrophysical Journal 185 (1973): 635-648.
  * [Tr1] D Treschev, Evolution of slow variables in a priori unstable Hamiltonian systems, 2004 Nonlinearity 17, 1803
  * [Tr2] D Treschev, Arnold diffusion far from strong resonances in multidimensional a priori unstable Hamiltonian systems, 2012 Nonlinearity 25, 2717
  * [W] Wald, Robert M. General relativity. University of Chicago press, 2010.
  * [Wi] D. Wilkins, Bounded geodesics in the Kerr metric, Physical Review D, Vol 5, No. 4, 814-822, 1972,
  * [X] J. Xue, KAM and geodesic dynamics of blackholes, preprint.
  * [Xi] Xia, Z.: Melnikov method and transversal homoclinic points in the restricted three-body problem. J. Differ. Equ. 96(1), 170-184 (1992)


# A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld
counting method

Anders Martinsson111ETH Zürich<EMAIL_ADDRESS>
###### Abstract

We show that any triangle-free graph with maximum degree $\Delta$ has
chromatic number at most $\left(1+o(1)\right)\Delta/\log\Delta.$

##  1 Introduction

The Johansson-Molloy Theorem states that any triangle-free graph $G$ with
maximum degree $\Delta$ has chromatic number at most
$(1+o(1))\Delta/\ln\Delta$ as $\Delta\rightarrow\infty$. In an interesting new
development on this problem, a recent article by Hurley and Pirot [1] present
an elementary proof based on the Rosenfeld counting method [2]. In fact, their
result is quite a bit stronger in that it works even if the underlying graph
contains a moderate amount of triangles, it extends to list colorings, and
give explicit error terms. In this note, we will present a simplified version
of their proof in the case of triangle-free graphs. We prove the following.

######  Theorem 1.1.

For any $\varepsilon>0$ there exists a constant
$\Delta_{0}=\Delta_{0}(\varepsilon)$ such that any triangle-free graph with
maximum degree at most $\Delta\geq\Delta_{0}$ is
$\lceil(1+\varepsilon)\Delta/\ln\Delta\rceil$-colorable.

Let us start by fixing some notation. Let
$k=\lceil(1+\varepsilon)\Delta/\ln\Delta\rceil$ denote the number of colors,
and for any graph $G$, let $\mathcal{C}(G)$ the set of proper $k$-colorings of
$G$.

We will show this theorem following the format of Rosenfelds counting method,
by proving by induction that the number of proper colorings of a triangle-free
graph grows by a large factor whenever a vertex is added. To this end, let
$\ell=\ell(\Delta)$ be any function such that
$\ln\Delta\ll\ell=\Delta^{o(1)}$, for instance $\ell(\Delta)=\ln^{2}\Delta.$

######  Claim 1.2.

Let $\Delta$ be sufficiently large and let $G$ be any triangle-free graph with
maximum degree at most $\Delta$. Then
$|\mathcal{C}(G)|/|\mathcal{C}(G-v)|\geq\ell$ for any $v\in G$.

Note that this immediately implies Theorem 1.1. In fact, the number of proper
$k$-colorings of $G$ grows as $\ell^{|V(G)|}>0$.

We will prove Claim 1.2 by induction of the number of vertices in $G$. Note
that the statement is trivially true when $G$ consists of a single vertex. So
we may assume below that $G$ has at least two vertices and that $v\in G$
denotes an arbitrary but fixed vertex.

For any partial proper coloring $c$ of $G$, let $L_{c}(u)$ denote the set of
_available colors_ for $u$. That is, the set of colors not present in the
neighborhood of $u$. In other words, $L_{c}(u)$ is the set of colors we can
(re-)assign to $u$ while keeping the coloring proper. Note that this
definition holds _regardless_ of whether $u$ is already assigned a color.

The core of our argument is to study the behavior of a uniformly chosen proper
coloring $\mathbf{c}$ of the graph $G-v$. That is, $\mathbf{c}$ is taken
uniformly at random from $\mathcal{C}(G-v)$. We first note that the conclusion
of the theorem can be expressed in terms of the expectation of the number
$|L_{\mathbf{c}}(v)|$ of available colors for $v$ in $\mathbf{c}$. Observe
that each proper coloring of $G$ can be formed by taking a proper coloring of
$G-v$ and extending it by coloring $v$ in one of its available colors. Hence,
we have the equality

$\mathbb{E}[|L_{\mathbf{c}}(v)|]=\frac{\sum_{c\in\mathcal{C}(G-v)}|L_{c}(v)|}{|\mathcal{C}(G-v)|}=\frac{|\mathcal{C}(G)|}{|\mathcal{C}(G-v)|},$

which means that the claim follows if we can prove that, for sufficiently
large $\Delta,$ $\mathbb{E}|L_{\mathbf{c}}(v)|\geq\ell.$ In fact, we will show
the stronger statement that, whp as $\Delta\rightarrow\infty$, we have
$|L_{\mathbf{c}}(v)|\gg\ell$.

The proof of this is based on two observations about the distribution of
$\mathbf{c}$. Let $u$ be any neighbor of $v$ in $G$, and let $t\geq 0$ be a
number to be chosen later. By the induction hypothesis, we know (in fact, for
any vertex) that $|\mathcal{C}(G-v)|\geq\ell\cdot|\mathcal{C}(G-v-u)|.$ We
will use this to show that it is unlikely for $u$ to have only few available
colors in $\mathbf{c}$. Note that any proper coloring of $G-v$ in which $u$
has at most $t$ available colors can be formed by taking some proper coloring
of $G-v-u$ and coloring $u$ by picking one out of at most $t$ options. Hence,
there are at most $t\cdot|\mathcal{C}(G-v-u)|$ such colorings. Plugging in the
induction hypothesis as above, it follows that

$\mathbb{P}(|L_{\mathbf{c}}(u)|\leq
t)\leq\frac{t\cdot|\mathcal{C}(G-v-u)|}{|\mathcal{C}(G-v)|}\leq\frac{t}{\ell}.$

In particular, this means that the expected number of neighbors of $v$ with at
most $t$ available colors in $\mathbf{c}$ is at most $t\Delta/\ell$. So if we
let $1\ll t\ll\ell/\ln\Delta$, it follows by Markov’s inequality that, with
high probability, all but at most $o(k)=o(\Delta/\ln\Delta)$ neighbors of $v$
have more than $t=\omega(1)$ available colors. Crucially, then only a small
fraction of colors will be unavailable for $v$ due to these vertices. Thus if
suffices to show that it is unlikely for the remaining neighbors of $v$ to
block too many of the other $k-o(k)$ colors.

Second, letting $G_{0}:=G-v-N(v)$, we consider the distribution of
$\mathbf{c}$ conditioned on $\mathbf{c}|_{G_{0}}=c_{0}$ for some
$c_{0}\in\mathcal{C}(G_{0})$. Observe that, as $G$ is triangle-free, there
cannot be any edges between two vertices in $N(v)$. Thus, for any $u\in N(v)$,
we have that $L_{\mathbf{c}}(u)$ is completely determined by $c_{0}$ according
to $L_{c_{0}}(u)$. Moreover, any $c\in\mathcal{C}(G-v)$ such that
$c|_{G_{0}}=c_{0}$ can be constructed from $c_{0}$ by, for each $u\in N(v)$,
color $u$ by an arbitrary color in $L_{c_{0}}(u)$. As $\mathbf{c}$ is
uniformly distributed, any such extension of $c_{0}$ is equally likely. Hence,
conditioned on $\mathbf{c}|_{G_{0}}=c_{0}$, we get that the colors of the
neighbors of $v$ are conditionally independent and uniformly chosen from the
respective sets $L_{c_{0}}(u)$. It remains to show that when
$L_{\mathbf{c}}(u)$ is large for most $u\in N(v)$, the set of colors present
in $N(v)$ behaves like a coupon collector process.

We have now reduced the problem to the following elementary statement: We are
given sets $L_{1},L_{2},\dots,L_{d}\subseteq[k]$ for some $d\leq\Delta$ where
all but $o(k)$ sets satisfies $|L_{i}|>t=\omega(1),$ and random variables
$X_{1}\in L_{1}$, …, $X_{d}\in L_{d}$ chosen independently and uniformly from
the respective sets. We wish to show that, whp,
$\mathbf{X}:=[k]\setminus\\{X_{1},X_{2},\dots X_{d}\\}$ contains $\gg\ell$
elements.

Note first that the events $j\in\mathbf{X}$ for $j\in[k]$ are negatively
correlated. This is intuitively clear as if some number $j$ never appears
among $X_{1},\dots,X_{d}$, then any $X_{i}$ such that $j\in L_{i}$ is
consequently more likely to hit any value in $L_{i}\setminus\\{j\\}$. It
follows that $\operatorname*{Var}(|\mathbf{X}|)\leq\mathbb{E}|\mathbf{X}|$, so
by Chebyshev’s inequality it suffices to show that
$\mathbb{E}|\mathbf{X}|\gg\ell$.

Condition on the values of $X_{i}$ for each $i$ such that $|L_{i}|\leq t$, and
let $B$ be the set of colors assigned to these variables. Then $|B|=o(k).$ By
linearity of expectation, the conditional expected value of $|\mathbf{X}|$
given these values is

$\sum_{j\in[k]\setminus B}\prod_{\begin{subarray}{c}L_{i}\ni j\\\
|L_{i}|>t\end{subarray}}\left(1-\frac{1}{|L_{i}|}\right).$

It only remains to find a natural lower bound to this expression. By applying
the AM-GM inequality to the right-hand side sum, we can lower bound the
previous expression by

$(k-|B|)\left(\prod_{j\in[k]\setminus B}\prod_{\begin{subarray}{c}L_{i}\ni
j\\\
|L_{i}|>t\end{subarray}}\left(1-\frac{1}{|L_{i}|}\right)\right)^{1/(k-|B|)}.$

Now, by reordering the products, we get

$\prod_{i:|L_{i}|>t}\prod_{j\in L_{i}\setminus
B}\left(1-1/|L_{i}|\right)\geq\left((1-1/t)^{t}\right)^{\Delta}=e^{-\left(1+O(1/t)\right)\cdot\Delta},$

meaning we can further lower bound the above expression by

$(k-|B|)\exp\left(-\frac{\left(1+o(1)\right)\cdot\Delta}{k-|B|}\right)=\Theta\left(\frac{\Delta}{\ln\Delta}\right)\cdot\exp\left(-\frac{1+o(1)}{1+\varepsilon}\ln\Delta\right)\geq\Delta^{\varepsilon/(1+\varepsilon)-o(1)},$

which is clearly $\gg\ell$, as desired. ∎

We end this note with two short remarks. First, by carefully choosing
parameters $\ell$ and $t$ in the argument, it is possible to let $\varepsilon$
depend on $\Delta$ according to
$\varepsilon=\Omega(\log\log\Delta/\log\Delta)$. Second, it is strictly
speaking not needed to argue for concentration of $|\mathbf{X}|$ in the proof.
As one only wishes to conclude that $|L_{\mathbf{c}}(v)|$ is large in
expectation, estimating $\mathbb{E}|\mathbf{X}|$ suffices on its own.
Nevertheless, we have chosen to write the proof with concentration as we find
the statement that $|L_{\mathbf{c}}(v)|$ is large whp intuitively simpler than
that
$\mathbb{E}\Big{[}|L_{\mathbf{c}}(v)\,|\Big{|}\,\mathbf{c}|_{G_{0}}\Big{]}$ is
large whp.

## Acknowledgements

The author thanks François Pirot and Eoin Hurley for helpful feedback.

## References

  * [1] Eoin Hurley, and François Pirot, A first moment proof of the Johansson-Molloy theorem, preprint available at https://arxiv.org/abs/2109.15215, 2021+.
  * [2] Matthieu Rosenfeld, Another Approach to Non-Repetitive Colorings of Graphs of Bounded Degree, Electronic Journal of Combinatorics 27(3), 2020.