# ReconVAT: A Semi-Supervised Automatic Music Transcription Framework for Low-
Resource Real-World Data

Kin Wai Cheuk Institute of High Performance Computing (IHPC), Agency for
Science, Technology and Research (A*STAR) ,  Dorien Herremans  Information
Systems Technology and Design
Singapore University of Technology and DesignSingapore0000 kinwai˙cheuk,
<EMAIL_ADDRESS>and  Li Su  Institute of Information
Science
Academia SinicaTaiwan0000<EMAIL_ADDRESS>
(2021)

###### Abstract.

Most of the current supervised automatic music transcription (AMT) models lack
the ability to generalize. This means that they have trouble transcribing
real-world music recordings from diverse musical genres that are not presented
in the labelled training data. In this paper, we propose a semi-supervised
framework, ReconVAT, which solves this issue by leveraging the huge amount of
available unlabelled music recordings. The proposed ReconVAT uses
reconstruction loss and virtual adversarial training. When combined with
existing U-net models for AMT, ReconVAT achieves competitive results on common
benchmark datasets such as MAPS and MusicNet. For example, in the few-shot
setting for the string part version of MusicNet, ReconVAT achieves F1-scores
of 61.0% and 41.6% for the note-wise and note-with-offset-wise metrics
respectively, which translates into an improvement of 22.2% and 62.5% compared
to the supervised baseline model. Our proposed framework also demonstrates the
potential of continual learning on new data, which could be useful in real-
world applications whereby new data is constantly available.

semi-supervised training, virtual adversarial training, audio processing,
automatic music transcription, music information retrieval

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
29th ACM International Conference on Multimedia; October 20–24, 2021; Virtual
Event, China††booktitle: Proceedings of the 29th ACM International Conference
on Multimedia (MM ’21), October 20–24, 2021, Virtual Event, China††price:
15.00††doi: 10.1145/3474085.3475405††isbn: 978-1-4503-8651-7/21/10††ccs:
Applied computing Sound and music computing††ccs: Computing methodologies
Semi-supervised learning settings††ccs: Computing methodologies Neural
networks

##  1\. Introduction

Automatic Music Transcription (AMT), is a fundamental problem in the field of
Music Information Retrieval (MIR). According to the definition from the field
of Music Information Retrieval (MIR) (Benetos et al., 2019), AMT aims at
transcribing music audio files into symbolic representations such as piano
rolls (Cemgil, 2004) or music scores (Carvalho and Smaragdis, 2017; Román et
al., 2018, 2019), which is very similar to Automatic Speech Recognition (ASR)
(Amodei et al., 2016; Chan et al., 2016). These symbolic representations have
a wide range of applications including music indexing (Cuthbert and Ariza,
2010; Sun and Lee, 2017), music generation (Huang and Yang, 2020), music
recommendation system (MRS) (Chen and Chen, 2001; Meroño-Peñuela et al., 2017;
Yamaguchi and Fukumoto, 2019), music analysis (Kong et al., 2020; Jiang and
Dannenberg, 2019; Liumei et al., 2021), and automatic music accompaniment
(Magalhaes, 2015).

Recent advances in fully supervised deep learning have enabled AMT models
(Hawthorne et al., 2017, 2019; Kim and Bello, 2019; Kelz et al., 2019) to
achieve state-of-the-art performance for solo piano pieces, given sufficient
labelled training data. While acoustic audio recordings as well as the aligned
midi labels for piano music can be easily obtained by using a hybrid
acoustic/midi piano such as the Yamaha Disklavier (Emiya et al., 2010), this
is not the case for other musical instruments such as violin and clarinet. At
the time of writing, hybrid versions of these musical instruments are still
not available. They are either midi controllers that lack the capability to
produce original acoustic sound, or fully acoustic instruments without the
capability to capture the real-time midi performance. Therefore, the paired
acoustic and midi recordings for these instruments are very expensive to
obtain, and hence, very limited. Supervised models fail to function well for
these instruments.

Self-supervised or semi-supervised learning is an underexplored area in AMT.
Existing unsupervised models have only been applied to specific musical
instruments. For example, Berg-Kirkpatrick et al. (2014) proposed an
unsupervised graphical model using prerecorded key-wise piano samples to
reconstruct the original signal. Upon successful reconstruction, the model
could infer the transcription result via both the onset locations and the
piano samples for reconstructing the spectrogram. Choi and Cho (2019) also
employed a similar approach in their unsupervised drum transcription model.
This approach, however, only works when the musical instrument is a percussion
or plucked instrument type with a clear transient, immediately followed by a
natural decay (piano is considered as a percussion instrument due to the
hammering mechanism). Musical instruments which produce an increasing or
fluctuating amplitude after the transient are unable to be represented by a
fixed audio sample, and hence can not be properly transcribed using the above-
mentioned approach. Examples of such instruments include string instruments
that are capable of starting a long note softly followed by a crescendo
through gradually increasing the bow pressure; and woodwind instruments that
can sustain a note as long as the player’s lung capacity can handle.

In this paper, we propose a semi-supervised AMT framework based on virtual
adversarial training (VAT) that leverages unlabelled data to improve the
transcription accuracy with only a limited amount of labelled data. We
integrate the spectrogram reconstruction into this framework, which we refer
to as ReconVAT. ReconVAT works well on various musical instruments such as
piano, string instruments, as well as woodwind instruments. We also show that
our framework has important applications such as continual learning with new
unlabelled recordings, and being able to transcribe music genres that are
outside of the labelled training set. More importantly, all of this can be
achieved with only a small number of model parameters compared to existing
deep learning models for AMT as shown in Figure 1. This makes our framework
attractive and practically usable for real-world applications deployed on
mobile devices. To the best of our knowledge, this is the first semi-
supervised deep learning framework for instrument-agnostic AMT at the time of
writing.

The contributions of this paper can be summarized as follows:

  * •

We propose a semi-supervised framework for AMT that generalizes well across
_different kinds of musical instruments_.

  * •

We leverage existing models by integrating them into the proposed semi-
supervised framework to achieve state-of-the-art transcription accuracy for
low-resource scenario.

  * •

We demonstrate possible applications in continual learning on music genres
that are not present in the train set.

Figure 1. A scatter plot showing the note-wise F1-score and the number of
model parameters for different models trained on the string version of
MusicNet (see Section 4.2 for details).

A scatter plot showing the note-wise F1-score and the number of model
parameters for different models trained on the string version of MusicNet.

Figure 2. The left-hand side of the figure shows the modified version of the
AMT model proposed in (Cheuk et al., 2020) such that it supports onset
prediction. The right-hand side of the figure shows the proposed framework for
semi-supervised AMT. For simplicity, we omit the onset prediction in the
figure by showing the case when $i=\\{\text{post}\\}$. The region highlighted
in green is the unsupervised module which supports training not only on
labelled samples, but also on unlabelled samples.

ReconVAT, our proposed semi-supervised framework for AMT.

##  2\. Method

In this section, we will formulate automatic music transcription (AMT)
mathematically. Then we will introduce related work, and describe how to
combine both spectrogram reconstruction (Cheuk et al., 2020) and VAT (Miyato
et al., 2019) to be our proposed semi-supervised framework ReconVAT.

###  2.1. Problem Definition

The goal of AMT is to convert audio data into symbolic music data (Benetos et
al., 2013; Benetos et al., 2019). In this paper, we consider the case of
converting spectrograms into piano rolls. Given an input spectrogram
$X_{\text{spec}}\in[0,1]^{T\times F}$, where $T$ is the number of timesteps
and $F$ is the number of frequency bins, we want to have a model
$p(Y_{\text{post}}|X_{\text{spec}},\theta)$, with a set of trainable
parameters $\theta$, that infers the posteriorgram
$Y_{\text{post}}\in[0,1]^{T\times N}$. Here $N$ is the note range for the
musical instrument, for example, $N=88$ for piano transcription since there
are 88 keys on the keyboard. The ground truth piano roll
$Y_{\text{roll}}\in\\{0,1\\}^{T\times N}$ is the symbolic notation we want to
predict. This is done by simply applying a threshold (e.g. $0.5$) to the
$Y_{\text{post}}$.

###  2.2. Spectrogram Reconstruction

In Cheuk et al. (2020), the authors proposed a model consisting of a
transcriber $p(Y_{\text{post}}|X_{\text{spec}},\theta)$ and a reconstructor
$q(X_{\text{recon}}|Y_{\text{post}},\phi)$. The reconstructor uses the
posteriorgram generated from the transcriber as input to reconstruct the
spectrograms $X_{\text{recon}}$. Therefore, in addition to the transcription
loss $L_{\text{trans}}(Y_{\text{post}},Y_{\text{label}})$, there is also a
reconstruction $L_{\text{recon}}(X_{\text{recon}},X_{\text{spec}})$ to be
minimized.

The reconstructed spectrograms $X_{\text{recon}}$ are then used to train the
same transcriber $p(Y^{\prime}_{\text{post}}|X_{\text{recon}},\theta)$ again,
resulting in one extra transcription loss
$L_{\text{trans}}(Y^{\prime}_{\text{post}},Y_{\text{label}})$. Cheuk et al.
(2020) has shown that training the model in this manner results in a
consistently better model. Their reported results, however, are unable to beat
the state-of-the-art AMT models. We will show in Table 1 that their model can
be modified to compete with the state-of-the-art AMT models. Although it is
not demonstrated in their paper, they also claim that their model has the
potential to be trained in an unsupervised manner. We will therefore also show
in Section 2.4 that when combined with virtual adversarial training (Miyato et
al., 2019), we can modify the spectrogram reconstruction framework (Cheuk et
al., 2020) to be a semi-supervised model for AMT.

###  2.3. Virtual Adversarial Training

Virtual adversarial training (VAT), as presented by Miyato et al. (2019) is an
extended version of adversarial training (AT) proposed by Goodfellow et al.
(2015). In AT, labels are required to calculate the the adversarial vectors.
In the case where we do not have access to the labels, Miyato et al. (2019)
proved that the adversarial vector can be obtained via Equation (1):

(1)
$r^{\text{VAT}}_{\text{adv}}=\epsilon\left(\nabla_{r}D\left[p(Y_{\text{pred}}|X,\theta),p(Y_{\text{adv}}|X+r,\hat{\theta})\right]\right)\,,$

where $r$ is a randomly initialized noise vector, and $Y_{\text{adv}}$ is the
output obtained using the adversarial input $X_{\text{adv}}=X+r$.

By doing so, it is possible to perform adversarial training using unlabelled
datasets. Most existing literature applies VAT to static classifications
(Amodei et al., 2016; Chan et al., 2016; Park and Chang, 2019; Miyato et al.,
2016; Kuwahara et al., 2019; Kreyssig and Woodland, 2020). While SeqVAT (Chen
et al., 2020) is designed for sequential labelling, it is a one-hot prediction
system. To the best of our knowledge, ReconVAT is the first framework capable
of multi-hot sequential labelling for polyphonic AMT. In the next section, we
will describe how to combine both spectrogram reconstruction and VAT to obtain
a semi-supervised framework for AMT.

###  2.4. Proposed Framework – ReconVAT

The left-hand side of Figure 2 shows our modified version of the model
proposed by Cheuk et al. (2020). We improve it by introducing a two-channel
output, one channel for the onset prediction $Y_{\text{onset}}$, and another
channel for the frame feature extraction $Y_{\text{frame}}$. The posteriorgram
is obtained from a self-attention layer which takes the concatenation of
$Y_{\text{onset}}$ and $Y_{\text{frame}}$ as the input. This modification
increases the model’s flexibility. For example, if we want to also include the
offset prediction $Y_{\text{offset}}$, we can have a three-channel output
instead. For simplicity, we will only explore the case of one-channel (without
onset prediction) and two-channel (with onset prediction) prediction in this
paper. The implementation details will be discussed in Section 3.4.

The right-hand side of Figure 2 shows our proposed ReconVAT. It consists of
three branches. The framework starts with the middle branch where it takes
$X_{\text{spec}}$ as the input and outputs a posteriorgram $Y_{\text{post}}$.
The branch on the left then takes the $Y_{\text{post}}$ as its input and
generates a reconstructed spectrogram $X_{\text{recon}}$ using the
reconstructor $q(X_{\text{recon}}|Y_{\text{post}},\phi)$ mentioned in 2.2. The
reconstructed spectrogram $X_{\text{recon}}$ is passed to the same model again
to obtain another posteriorgram $Y^{\prime}_{\text{post}}$. The two
posteriorgrams $Y_{\text{post}}$ and $Y^{\prime}_{\text{post}}$ should be as
close to the label $Y_{\text{label}}$ as possible.

The branch on the right-hand side is the unsupervised module which uses VAT.
To obtain the adversarial spectrogram $X_{\text{adv}}$, we apply a modified
version of VAT that works better for AMT (Section 3.4). Using this adversarial
spectrogram, we obtain another posteriorgram $Y_{\text{post}}$ via the same
model.

For labelled spectrograms, all three branches are used. For unlabelled
spectrograms, we only use the middle and the right branches (highlighted in
green in Figure 2). By doing so, this allows us to train our model with
unlabelled data. This framework is trained by minimizing both the supervised
loss $L_{\text{l}}$ (Equation 5) and the unsupervised loss $L_{\text{ul}}$
which will be discussed in detail in Section 3.5.

##  3\. Experiments

In this section, we describe the datasets and the experiments for
demonstrating the power of our proposed semi-supervised framework ReconVAT.

###  3.1. MAPS dataset

The MAPS dataset (Emiya et al., 2010) consists of nine folders, each folder
contains 30 full-length midi recordings. In seven of these folders, the audio
recordings are synthesized from the midi annotations using different virtual
piano software such as Steinberg, Native Instruments, and Sampletekk. Only in
the folders ENSTDkAm and ENSTDkCl, the audio recordings are recorded
simultaneously with the midi recordings using a Yamaha Disklavier. We follow
the existing consensus (Hawthorne et al., 2017; Sigtia et al., 2015; Cheuk et
al., 2020; Kelz et al., 2019; Pedersoli et al., 2020) that the seven folders
containing artificially generated audio recordings should be used as the
training set, and the other two folders, ENSTDkAm and ENSTDkCl, as the test
set.

Since some music pieces appear in both the training and the test set, we
follow the existing literature (Sigtia et al., 2015; Hawthorne et al., 2017)
to remove overlapping songs from the training set that are also present in the
test set, thus reducing the size of the training set from 210 music pieces
down to 139 pieces. Following existing conventions (Sigtia et al., 2015;
Hawthorne et al., 2017, 2019; Cheuk et al., 2020), all audio recordings are
downsampled from $44.1$ kHz to $16$ kHz.

To demonstrate the effectiveness of our VAT model, we train our model using
the following three versions of the MAPS dataset:

####  3.1.1. Full version

This version uses all 139 available pieces from MAPS as the labelled training
set. To demonstrate the ability of leveraging unlabelled data using our VAT
model, we use the training set from MAESTRO (Hawthorne et al., 2019) as the
unlabelled dataset (967 music recordings). The labelled training batch size
$N_{\text{l}}$ and the unlabelled training batch size $N_{\text{ul}}$ are both
8.

####  3.1.2. Small version

In this version, only one folder (AkPnBcht, containing 23 non-overlapping
songs) from MAPS is used as the labelled training set. We keep using the same
967 music recordings from MAESTRO as our unlabelled set for our VAT model.
Again, $N_{\text{l}}$ and $N_{\text{ul}}$ are both 8 in this version.

####  3.1.3. One-shot version

Only one music recording (chp_op31 from the AkPnBcht folder) is used as the
labelled training set. The unlabelled set consists of the same 967 music
recordings from MAESTRO as the above two versions. Due to the fact that there
is only one labelled training sample, $N_{\text{l}}$ is 1 and the unlabelled
training batch size $N_{\text{ul}}$ remains 8.

###  3.2. MusicNet dataset

MusicNet (Thickstun et al., 2016) contains both audio recordings and
annotations of various types of musical instruments such as those from the
string family and the woodwind family. To prove that our model also works for
different types of musical instruments, we perform our experiments on the
following variations of MusicNet:

####  3.2.1. String version

In the official training set provided by MusicNet, there are 8 genres of music
that contain string instruments. We select only one piece from each genre from
the official training set, forming our own labelled training set. The
remaining pieces of each genre are used as the unlabelled training set for our
VAT framework. By doing so, there are eight labelled samples and 104
unlabelled samples in our training set. We pick four string pieces from the
official test set provided by MusicNet as our test set. The details of data
splitting can be found in the supplementary material22footnotemark: 2. The
labelled training batch size $N_{\text{l}}$ and the unlabelled training batch
size $N_{\text{ul}}$ are both 8.

####  3.2.2. Woodwind version

Similar to the string version, we pick only one piece from six different
woodwind genres from MusicNet as the labelled training set and use the
remaining pieces in each genre as the unlabelled training set. This results in
six labelled training samples and 21 unlabelled training samples. The official
test set provided by MusicNet contains only two pieces (1819, 2416) from the
woodwind family, which belong to the Pairs Clarinet-Horn-Bassoon genre. We use
these two pieces as our test set. Again, more details can be found
supplementary material22footnotemark: 2. $N_{\text{l}}$ is 1 and
$N_{\text{ul}}$ is 8 in this version.

###  3.3. Data Processing

We extract Mel spectrograms on-the-fly from the audio clips using a GPU-based
audio processing library nnAudio (Cheuk et al., 2020). Following Hawthorne et
al. (2017), we use a Hann window size of 2,048, a hop size of 512, and 229 Mel
bins as the parameters of our Mel spectrograms $X_{\text{spec}}$. To extract a
fixed length spectrogram, we crop the audio clips into segments of 327,680
sample points using random sampling during each iteration, which results in
Mel spectrogram with 640 timesteps, and 229 Mel frequency bins. We compress
the magnitude of the spectrograms by taking the natural logarithm and then
normalizing the magnitude for each spectrogram into the range $[0,1]$. i.e.
$X_{\text{spec}}\in[0,1]^{640\times 229}$.

As for our ground truth labels, we extract the onset, duration, and pitch
information from the midi annotations to produce tsv files for the ground
truth. These tsv files are read and converted into piano rolls in the form of
a binary matrix $Y_{\text{label}}\in\\{0,1\\}^{640,F}$. Since most musical
instruments in the dataset are within the 88 notes range (note A0 to note C8),
we use $F=88$ in all our experiments.

###  3.4. Implementation Details

All models and experiments, including the baseline models, are implemented in
PyTorch. To ensure transparency and fairness, we train all our models without
tricks such as label smoothing (Wu et al., 2020), weighted cross entropy
(Hawthorne et al., 2017), and focal loss (Wu et al., 2019; Lin et al., 2017).
We believe that these tricks would in general improve the the transcription
accuracy, and it is beyond the scope of this paper to explore this.

We adopt U-net models specifically designed for pitch detection (Cheuk et al.,
2020; Hung et al., 2019) and integrate them into the VAT framework (Miyato et
al., 2019). While we follow mostly the same design as in (Cheuk et al., 2020),
we modify the final layer of the decoder so that it has the flexibility to
output two channels as shown in Figure 2. One of the channels is fed to a
fully connected layer with sigmoid activation to predict the onsets
$Y_{\text{onset}}\in[0,1]^{T\times F}$, and the other channel is fed to a
linear fully connected layer to obtain the features
$Y_{\text{frame}}\in\mathbb{R}^{T\times F}$. The concatenated output
$Y_{\text{onset}}\bigoplus Y_{\text{frame}}$ is fed to a relative local 1D
self-attention layer (Shaw et al., 2018; Ramachandran et al., 2019) to obtain
the posteriorgram $Y_{\text{post}}\in[0,1]^{T\times 88}$. We binarize the
posteriorgram with a threshold of $0.5$ to obtain the predicted piano roll
$Y_{\text{roll}}\in\\{0,1\\}^{T\times 88}$. If the two-channel output is used,
we follow the inference method from the Onsets and Frames model (Hawthorne et
al., 2017) to obtain a refined piano roll by using both $Y_{\text{onset}}$ and
$Y_{\text{frame}}$ to filter out notes that do not have a onset. Otherwise, we
directly use the posteriorgram to obtain the piano roll. In addition, we also
replace all of the LSTM layers in (Cheuk et al., 2020) with local relative
self-attention layers, since it has been shown that self-attention layers
perform as good as LSTM layers while providing the extra benefit of being able
to train in parallel (Won et al., 2019; Wu et al., 2020).

We also modify the original VAT method (Miyato et al., 2019) so that it works
better for AMT. Firstly, since polyphonic AMT is a timestep-wise multiclass
classification problem (multiple pitches can occur at the same time), we
replace the Kullback–Leibler divergence (KL-div) with binary cross entropy
(BCE) when calculating the local distributional smoothness (LDS). Secondly, we
normalise the adversarial vector $r_{\text{adv}}$ along the timestep dimension
as shown in Equation (2):

(2) $r_{\text{adv}}=\epsilon\begin{bmatrix}\frac{g_{1}}{{\lVert
g_{1}\rVert}_{2}},\frac{g_{2}}{{\lVert
g_{2}\rVert}_{2}},\cdots,\frac{g_{T}}{{\lVert g_{T}\rVert}_{2}}\end{bmatrix}$

where $\epsilon$ is a parameter that controls the magnitude of the adversarial
vector $r_{\text{adv}}$, and $g_{t}$ for $1\leq t\leq T$ is the timestep-wise
gradient obtained from Equation (3)

(3)
$g=\nabla_{r}\sum_{i}\text{BCE}\left[p(Y_{\text{i}}|X_{\text{spec}},\hat{\theta}),p(Y_{\text{adv}}|X_{\text{spec}}+r,\hat{\theta})\right]\,.$

If the onsets prediction module is included, then
$i=\\{\text{onset},\text{post}\\}$. Otherwise, there is only one term in
Equation (3), i.e. $i=\\{\text{post}\\}$. As in (Miyato et al., 2019), the
weight of the model is considered as a constant $\hat{\theta}$ when
calculating the gradient $g$.

Once we obtain the adversarial vector $r_{\text{adv}}$, we can calculate the
LDS. By the same logic as above, the LDS can contain either one or two terms
depending on the model output:

(4)
$\text{LDS}_{*}=\frac{\sum_{i}\text{BCE}\left[p(Y_{\text{i}}|X^{*}_{\text{spec}},\hat{\theta}),p(Y_{\text{adv}}|X^{*}_{\text{spec}}+r_{\text{adv}},\theta)\right]}{N_{*}}\,.$

From Equation 4, we can see that the label $Y_{i}^{\text{label}}$ is not
required to calculate the LDS. Therefore, LDS is an unsupervised loss that can
be calculated using both labelled spectrograms $X^{\text{l}}_{\text{spec}}$
and unlabelled spectrograms $X^{\text{ul}}_{\text{spec}}$. We will denote the
LDS calculated using $X^{\text{l}}_{\text{spec}}$ as $\text{LDS}_{\text{l}}$
and the LDS calculated using $X^{\text{ul}}_{\text{spec}}$ as
$\text{LDS}_{\text{ul}}$. Unlike the original VAT (Miyato et al., 2019), we
normalise $\text{LDS}_{\text{l}}$ and $\text{LDS}_{\text{ul}}$ by its
respective batch size $N_{\text{l}}$ and $N_{\text{ul}}$, rather than summing
both $\text{LDS}_{\text{l}}$ and $\text{LDS}_{\text{ul}}$ together and
normalize with $N_{\text{l}}+N_{\text{ul}}$. By doing so, we prevent
$N_{\text{ul}}$ from interfering with $\text{LDS}_{\text{l}}$ and
$N_{\text{l}}$ from interfering with $\text{LDS}_{\text{ul}}$.

###  3.5. Training Objective and Optimization

As mentioned in Section 3.4, we have the supervised objective $L_{\text{l}}$
that requires labels, and the unsupervised objective $L_{\text{ul}}$ that does
not require any label. The final objective $L$ being minimized during training
contains three terms as shown in Equation (7):

(5)
$L_{\text{l}}=\sum_{i}\text{BCE}\left[Y_{i},Y^{\text{label}}_{i}\right]+\sum_{i}\text{BCE}\left[Y^{\text{recon}}_{i},Y^{\text{label}}_{i}\right]$

(6) $L_{\text{ul}}=\frac{\text{LDS}_{\text{l}}+\text{LDS}_{\text{ul}}}{2}$

(7) $L=L_{\text{l}}+\alpha L_{\text{ul}}+L_{\text{recon}}$

where $\alpha$ is the weighting for $L_{\text{ul}}$, which is set to $1$
throughout all our experiments; $L_{\text{recon}}$ is the reconstruction loss
mentioned in Section 2.2. We observe the same model behaviour as reported in
(Miyato et al., 2019), that is, controlling the $\epsilon$ in Equation (2)
alone is sufficient to control the model performance without the need to
change $\alpha$.

To minimize the objective $L$, we use Adam (Kingma and Ba, 2014) optimizer
with a learning rate of $0.001$ and a learning rate decay of $2\%$ every 1,000
iterations. When training, our framework includes three forward passes during
each iteration. One forward pass for $L_{\text{l}}$, one forward pass for
$\text{LDS}_{\text{l}}$, and one forward pass for $\text{LDS}_{\text{ul}}$. We
define one epoch as 10 iterations. During the parameter search, we split our
training set into 80% for training and 20% for validating. The optimal value
for $\epsilon$ in Equation (2 is mostly within the range between $1$ and $2$,
and depends on the model architecture and the dataset. This value can be
easily obtained after a few trials.

###  3.6. Evaluation Metrics

Following existing literature (Cheuk et al., 2020, 2021; Hawthorne et al.,
2017, 2019; Kim and Bello, 2019; Kelz et al., 2019), we report the frame-wise,
note-wise, and note-with-offset-wise metrics to evaluate our model performance
comprehensively. For note-wise metric, we use a onset tolerance of 50ms; for
note-with-offset-wise metric, we use an offset tolerance of 50ms or $20\%$ of
the note duration, whichever is larger (Bay et al., 2009). Readers are
referred to Cheuk et al. (2021) which explains the differences between these
metrics in detail in their Section IV-C. In our experiments, we use the
implementations from mir_eval111https://github.com/craffel/mir_eval to
calculate and report the above-mentioned metrics.

##  4\. Results

###  4.1. Effectiveness of VAT

We compare our proposed models to the Onsets and Frames model (Hawthorne et
al., 2017) and the Multi-Instrument AMT model (Wu et al., 2020) as they show
good performance on the MAPS and MusicNet datasets respectively. We exclude
the models proposed by Pedersoli et al. (2020) and Thickstun et al. (2017) in
our results below since their performance is worse than the Multi-Instrument
AMT model (Wu et al., 2020). We use R to represent the reconstruction module,
and O to represent the onset module. Therefore U-net-RO means that the U-net
model contains both a reconstruction and onset module. The columns represent
the precision (P), recall (R), and F1-score for each of the metrics mentioned
in Section 3.6. Our proposed models and the baseline models are trained on the
same labelled data, and only the proposed semi-supervised models are able to
leverage the unlabelled data mentioned in Section 3.

####  4.1.1. Full MAPS

We can see that when using the VAT (row A3-A4, A7, A8), all three metrics
generally improve compared to their respective counterparts without the VAT
(row A1-A2, A5, A6). When using onset inference (A5-A8), the note-wise and
note-with-offset-wise metrics are improved by at least 7 percentage points.
The model using both the onset inference as well as our proposed framework
(row A8) performs as good as the state-of-the-art Onsets and Frames model
(Hawthorne et al., 2017) (row 9) for this dataset.

####  4.1.2. Small MAPS

The middle part of Table 1 shows that when the number of labelled training
samples is reduced by over $80\%$ from $139$ to $23$ audio clips, the
advantage of the VAT module becomes more obvious. Similar for the full MAPS
dataset, the models with VAT module outperform their counterparts that do not
use VAT. Moreover, our proposed framework (row B8) outperforms the Onsets and
Frames model (B9) by 6, 5.1, 4.4 percentage points in terms of frame-wise,
note-wise, and note-with-offset-wise F1-scores, which can be translated into
improvements in performance of $11.5\%$, $8.1\%$, and $14.1\%$ respectively.

####  4.1.3. One-shot MAPS

The bottom part of Table 1 shows that when we reduce the number of labelled
training audio clip even further to only one, our proposed framework (C8)
outperforms the Onsets and frames model (C9) by 23.7, 17, and 12.9 percentage
points.

Between the models that use and do not use onset inference, we can see that
onset inference has the tendency of decreasing the frame-wise F1-score while
improving the note-wise F1-scores. This is due to the unreliability of the
frame-wise metric (Hawthorne et al., 2017; Cheuk et al., 2021). Cheuk et al.
(2021) has provided a few examples and shown that a high frame-wise score does
not guarantee a good transcription. Nonetheless, these three experiments have
shown that VAT is a very effective semi-supervised method, that allows the use
of unlabelled training samples to greatly improve the model performance in
cases where the number of labelled samples is scarce.

####  4.1.4. String MusicNet

The top section of Table 2 shows the performance of our proposed framework on
the string subset of MusicNet (3.2.1). Interestingly, using the onset
inference (row D1-4 and D9) does not improve the transcription accuracy in
this setting, on the contrary, it worsens the model performance. Although most
models with the VAT outperform their counterparts without the VAT, U-net-RO
VAT on row B9 performs worse than its counterpart without the VAT. There are
two possible reasons for this. First, we believe that the onset inference only
works well for piano only, and it cannot generalize well to other musical
instruments such as those from the string and the woodwind family. Second, we
believe that the onset labels for MusicNet are not completely accurate, since
the labels are generated using dynamic time warping (DTW) (Thickstun et al.,
2017). Therefore, inaccurate onset labels might confuse the VAT. Using no
labels might be better than using inaccurate labels, which is one of the
advantages of using VAT.

Now, let us consider models (row D5-D8) that do not use onset inference. We
will use the Multi-Instrument AMT model (row D10) (Wu et al., 2020), which is
the state-of-the-art model for the MusicNet dataset at the time of writing, as
the baseline model. Since the baseline model (Wu et al., 2020) is much deeper
than the U-net model (row D5), it outperforms the U-net model. By applying the
reconstruction module to the U-net model (row D6), the U-net model begins to
outperform the baseline model. When we further apply VAT to the U-net models
(row D7-D8), the transcription accuracy becomes even better. The best model,
U-net-R VAT (row D8), outperforms the baseline model by 3.9, 11.1, and 11.3
percentage points in terms of frame-wise, note-wise, and note-with-offset-wise
metrics.

####  4.1.5. Woodwind MusicNet

The bottom section of Table 2 shows the results for the woodwind subset of
MusicNet (Section 3.2.2). Since the Onsets and Frames model does not work well
for this dataset either, we did not spend time experimenting with it. Just
like all of the results reported above, the VAT module is very effective in
improving the transcription accuracy. The best model being the one with both
the reconstruction and the VAT module (row E4), and it outperforms the
baseline model by $10.3$, $6.9$ percentage points in terms of note-wise and
note-with-offset-wise metrics. The improvement for the frame-wise metrics is
not obvious, however, we must keep in mind that this is not a reliable metric
to evaluate the transcription accuracy as pointed out previously in Section
3.6 as well as existing literature (Cheuk et al., 2021; Hawthorne et al.,
2017).

###  4.2. Model Compactness

A comparison of number of trainable model parameters for the baseline models
and the proposed models is shown in Figure 1. It can be seen from the figure
that a deep model does not necessarily yield a high transcription accuracy
when the labelled training data is limited. The Onsets and Frames model
(Hawthorne et al., 2017) and the Prestack-Unet (Pedersoli et al., 2020) have a
high number of parameters, yet they do not perform well when the labelled data
is scarce. While Thickstun’s model (Thickstun et al., 2017) performs better
than the two baseline models, its number of parameters is 10 times more than
our proposed framework (U-net-R VAT). We use the Resnet-18 version of
Prestack-Unet since the Resnet-32 version is too huge to run on our GPU.
Another baseline model, the Multi-Instrument AMT model, performs better than
the plain U-net model. With VAT, however, the U-net models already outperform
the baseline model while keeping the number of trainable parameters low. We
can also see that the VAT improves the model performance without adding extra
parameters to the model. Therefore, VAT is a very effective method to improve
the transcription accuracy by leveraging unlabelled training data when the
labelled training data is limited.

Table 1. Transcription accuracy (mean + STD) in terms of different metrics and
their respective precision (P), recall (R), and F1-score (F1) when training on
different variations of the MAPS dataset. The accuracy values are averaged
over the test clips in the dataset.

|  | Frame | Note | Note w/ offset
---|---|---|---|---
| Full | P | R | F1 | P | R | F1 | P | R | F1
A1 |  U-net (Cheuk et al., 2020) | 84.6 ± 6.0 | 70.8 ± 8.9 | 76.7 ± 6.5 | 55.8 ± 12.6 | 62.0 ± 11.9 | 58.4 ± 11.7 | 34.5 ± 11.3 | 38.5 ± 12.0 | 36.2 ± 11.4
A2 |  U-net-R (Cheuk et al., 2020) | 86.2 ± 6.2 | 72.7 ± 10.0 | 78.4 ± 7.0 | 68.5 ± 10.5 | 61.0 ± 13.1 | 64.2 ± 11.4 | 45.5 ± 11.1 | 40.8 ± 12.9 | 42.8 ± 11.9
A3 | U-net VAT | 86.6 ± 5.4 | 71.5 ± 9.4 | 77.9 ± 6.7 | 64.5 ± 13.2 | 64.2 ± 12.6 | 64.0 ± 12.3 | 40.8 ± 11.6 | 40.9 ± 12.1 | 40.6 ± 11.5
A4 | U-net-R VAT | 88.8 ± 6.0 | 72.7 ± 9.0 | 79.5 ± 6.5 | 74.0 ± 9.3 | 63.3 ± 13.3 | 67.9 ± 11.2 | 49.7 ± 10.1 | 42.9 ± 12.5 | 45.8 ± 11.3
A5 | U-net-O | 89.6 ± 6.0 | 58.8 ± 9.9 | 70.4 ± 7.5 | 85.8 ± 7.8 | 66.3 ± 11.0 | 74.5 ± 9.2 | 53.1 ± 9.5 | 41.5 ± 11.3 | 46.4 ± 10.6
A6 | U-net-RO | 89.9 ± 6.6 | 60.4 ± 10.8 | 71.6 ± 8.3 | 86.1 ± 7.9 | 67.3 ± 11.2 | 75.2 ± 9.2 | 52.8 ± 10.1 | 41.7 ± 11.6 | 46.4 ± 10.9
A7 | U-net-O VAT | 90.9 ± 6.1 | 60.5 ± 9.5 | 72.2 ± 7.5 | 89.8 ± 8.3 | 65.0 ± 11.1 | 75.1 ± 9.5 | 58.7 ± 9.9 | 42.9 ± 11.3 | 49.4 ± 10.8
A8 | U-net-RO VAT | 85.9 ± 7.2 | 72.0 ± 8.7 | 77.9 ± 6.5 | 80.9 ± 7.0 | 70.6 ± 11.2 | 75.1 ± 8.6 | 54.3 ± 9.8 | 47.6 ± 11.8 | 50.5 ± 10.6
A9 |  O&F (Hawthorne et al., 2017) | 89.3 ± 6.4 | 65.6 ± 9.7 | 75.2 ± 7.3 | 85.2 ± 7.8 | 73.3 ± 11.4 | 78.6 ± 9.3 | 53.8 ± 9.8 | 46.7 ± 12.0 | 49.8 ± 10.9
| Small | P | R | F1 | P | R | F1 | P | R | F1
B1 |  U-net (Cheuk et al., 2020) | 75.4 ± 6.6 | 57.1 ± 9.6 | 64.5 ± 7.3 | 35.4 ± 8.3 | 57.5 ± 11.6 | 43.5 ± 8.9 | 17.0 ± 6.9 | 27.6 ± 10.6 | 20.9 ± 8.0
B2 |  U-net-R (Cheuk et al., 2020) | 81.2 ± 6.1 | 61.1 ± 11.1 | 69.1 ± 8.1 | 51.0 ± 10.3 | 61.3 ± 12.4 | 55.3 ± 10.6 | 26.2 ± 9.8 | 31.8 ± 12.4 | 28.6 ± 10.7
B3 | U-net VAT | 79.1 ± 6.6 | 56.9 ± 11.7 | 65.4 ± 8.7 | 52.4 ± 11.9 | 60.1 ± 12.6 | 55.5 ± 11.3 | 26.2 ± 9.8 | 30.3 ± 11.6 | 27.8 ± 10.3
B4 | U-net-R VAT | 79.7 ± 6.1 | 59.9 ± 11.0 | 67.7 ± 7.8 | 57.2 ± 11.9 | 61.0 ± 12.0 | 58.6 ± 11.1 | 29.2 ± 10.3 | 31.3 ± 11.3 | 30.0 ± 10.5
B5 | U-net-O | 88.3 ± 6.3 | 38.4 ± 10.2 | 52.6 ± 9.8 | 81.9 ± 7.9 | 50.1 ± 11.3 | 61.6 ± 9.8 | 41.0 ± 10.1 | 25.6 ± 10.1 | 31.2 ± 10.2
B6 | U-net-RO | 88.0 ± 6.3 | 44.9 ± 11.2 | 58.5 ± 10.1 | 83.4 ± 8.7 | 55.8 ± 12.2 | 66.3 ± 10.3 | 42.8 ± 10.3 | 29.2 ± 10.7 | 34.4 ± 10.6
B7 | U-net-O VAT | 89.5 ± 6.6 | 41.0 ± 10.5 | 55.4 ± 10.0 | 86.8 ± 8.8 | 52.3 ± 12.1 | 64.7 ± 10.7 | 44.0 ± 10.8 | 27.0 ± 10.4 | 33.1 ± 10.7
B8 | U-net-RO VAT | 90.0 ± 6.2 | 43.9 ± 10.6 | 58.2 ± 9.7 | 86.2 ± 8.6 | 57.1 ± 11.5 | 68.2 ± 10.0 | 44.6 ± 11.7 | 30.0 ± 11.0 | 35.6 ± 11.3
B9 |  O&F (Hawthorne et al., 2017) | 89.7 ± 5.8 | 37.7 ± 10.4 | 52.2 ± 10.4 | 85.3 ± 8.6 | 51.2 ± 13.1 | 63.1 ± 11.4 | 41.8 ± 10.5 | 25.5 ± 10.2 | 31.2 ± 10.4
| One-shot | P | R | F1 | P | R | F1 | P | R | F1
C1 |  U-net (Cheuk et al., 2020) | 61.9 ± 5.8 | 41.8 ± 9.1 | 49.2 ± 6.9 | 24.7 ± 7.6 | 49.6 ± 10.6 | 32.2 ± 7.9 | 8.8 ± 5.6 | 17.0 ± 8.5 | 11.3 ± 6.5
C2 |  U-net-R (Cheuk et al., 2020) | 74.8 ± 5.9 | 41.2 ± 10.4 | 52.2 ± 8.5 | 33.6 ± 9.4 | 54.5 ± 11.5 | 40.7 ± 8.8 | 12.5 ± 7.2 | 19.8 ± 10.0 | 15.0 ± 8.1
C3 | U-net VAT | 75.6 ± 6.6 | 46.1 ± 11.1 | 56.2 ± 9.0 | 42.7 ± 11.0 | 55.2 ± 12.7 | 47.1 ± 9.6 | 17.1 ± 7.8 | 22.1 ± 9.7 | 18.9 ± 8.1
C4 | U-net-R VAT | 71.6 ± 6.0 | 43.6 ± 9.5 | 53.3 ± 7.3 | 36.4 ± 8.5 | 61.5 ± 12.0 | 45.2 ± 8.5 | 13.6 ± 6.6 | 22.8 ± 10.4 | 16.8 ± 7.7
C5 | U-net-O | 87.7 ± 7.2 | 17.4 ± 7.0 | 28.4 ± 9.3 | 85.7 ± 6.6 | 27.7 ± 10.0 | 40.9 ± 11.3 | 34.5 ± 10.6 | 11.4 ± 6.1 | 16.8 ± 7.7
C6 | U-net-RO | 87.7 ± 7.5 | 21.4 ± 9.0 | 33.4 ± 11.1 | 82.0 ± 7.1 | 33.4 ± 11.7 | 46.3 ± 11.9 | 34.4 ± 10.0 | 14.6 ± 7.9 | 20.0 ± 9.0
C7 | U-net-O VAT | 72.9 ± 9.4 | 22.9 ± 8.8 | 33.5 ± 9.1 | 57.9 ± 10.2 | 43.6 ± 12.4 | 47.9 ± 7.6 | 17.1 ± 7.8 | 13.0 ± 7.0 | 14.2 ± 6.8
C8 | U-net-RO VAT | 86.1 ± 6.8 | 31.4 ± 9.8 | 45.0 ± 10.3 | 77.2 ± 9.8 | 51.5 ± 12.4 | 60.7 ± 9.6 | 31.4 ± 10.4 | 21.1 ± 9.1 | 24.8 ± 9.2
C9 |  O&F (Hawthorne et al., 2017) | 88.0 ± 6.8 | 12.4 ± 4.8 | 21.3 ± 7.2 | 83.5 ± 8.2 | 30.5 ± 10.4 | 43.7 ± 11.2 | 23.1 ± 11.4 | 8.3 ± 4.7 | 11.9 ± 6.3

Table 2. Transcription accuracy (mean ± STD) in terms of different metrics and
their respective precision (P), recall (R), and F1-score (F1) when training on
the different variations of the MusicNet dataset. The accuracy values are
averaged over the test clips in the dataset.

|  | Frame | Note | Note w/ offset
---|---|---|---|---
| Strings | P | R | F1 | P | R | F1 | P | R | F1
D1 | U-net-O | 70.0 ± 8.4 | 25.3 ± 13.4 | 35.7 ± 13.8 | 59.9 ± 10.7 | 24.6 ± 13.0 | 33.9 ± 13.6 | 35.4 ± 11.3 | 15.0 ± 9.9 | 20.5 ± 11.0
D2 | U-net-RO | 79.1 ± 1.1 | 39.3 ± 18.7 | 50.1 ± 16.6 | 68.5 ± 12.3 | 39.4 ± 17.2 | 48.6 ± 16.1 | 49.0 ± 17.1 | 29.9 ± 17.8 | 36.3 ± 18.5
D3 | U-net-O VAT | 65.2 ± 18.9 | 27.6 ± 13.5 | 38.2 ± 15.6 | 52.7 ± 14.2 | 27.8 ± 14.5 | 35.7 ± 14.9 | 31.5 ± 13.4 | 17.4 ± 12.6 | 22.0 ± 13.5
D4 | U-net-RO VAT | 78.0 ± 4.0 | 36.9 ± 10.5 | 49.5 ± 10.1 | 69.6 ± 13.7 | 37.6 ± 11.4 | 48.4 ± 11.9 | 50.1 ± 18.3 | 27.8 ± 13.4 | 35.4 ± 15.4
D5 |  U-net (Cheuk et al., 2020) | 67.1 ± 6.9 | 50.7 ± 12.9 | 57.4 ± 10.5 | 41.8 ± 12.5 | 46.1 ± 12.7 | 43.7 ± 12.5 | 24.6 ± 13.4 | 26.7 ± 14.0 | 25.6 ± 13.7
D6 |  U-net-R (Cheuk et al., 2020) | 71.7 ± 2.9 | 62.8 ± 10.6 | 66.6 ± 6.9 | 53.1 ± 10.7 | 57.4 ± 11.9 | 55.1 ± 11.1 | 37.6 ± 14.1 | 40.9 ± 16.4 | 39.1 ± 15.2
D7 | U-net VAT | 76.1 ± 7.2 | 52.4 ± 11.9 | 61.7 ± 10.2 | 58.1 ± 13.9 | 51.2 ± 15.1 | 54.2 ± 14.3 | 39.6 ± 17.8 | 35.4 ± 18.4 | 37.2 ± 18.1
D8 | U-net-R VAT | 78.9 ± 4.8 | 60.7 ± 9.8 | 68.4 ± 7.7 | 63.6 ± 13.8 | 58.8 ± 14.3 | 61.0 ± 13.8 | 43.3 ± 18.8 | 40.2 ± 18.9 | 41.6 ± 18.7
D9 |  O&F (Hawthorne et al., 2017) | 75.3 ± 3.1 | 22.5 ± 12.0 | 33.1 ± 14.6 | 69.0 ± 15.8 | 22.6 ± 12.1 | 32.9 ± 14.8 | 41.7 ± 18.2 | 15.3 ± 11.2 | 21.7 ± 14.5
D10 |  Multi-Inst (Wu et al., 2020) | 71.4 ± 6.2 | 59.5 ± 13.1 | 64.5 ± 9.6 | 56.5 ± 16.7 | 45.1 ± 18.4 | 49.9 ± 17.8 | 33.7 ± 19.3 | 27.8 ± 18.4 | 30.3 ± 18.9
| Woodwinds | P | R | F1 | P | R | F1 | P | R | F1
E1 |  U-net (Cheuk et al., 2020) | 62.6 ± 9.6 | 65.7 ± 2.9 | 63.5 ± 3.7 | 33.6 ± 2.4 | 39.9 ± 1.1 | 36.4 ± 1.0 | 11.6 ± 1.4 | 13.7 ± 0.3 | 12.5 ± 0.9
E2 |  U-net-R (Cheuk et al., 2020) | 65.4 ± 6.7 | 71.4 ± 4.3 | 67.8 ± 1.7 | 40.5 ± 5.8 | 52.5 ± 0.6 | 45.4 ± 3.5 | 16.9 ± 5.2 | 21.3 ± 3.5 | 18.7 ± 4.7
E3 | U-net VAT | 69.0 ± 9.6 | 62.4 ± 1.2 | 65.1 ± 3.7 | 44.4 ± 3.1 | 40.5 ± 2.5 | 42.2 ± 0.0 | 16.1 ± 1.6 | 14.6 ± 0.5 | 15.3 ± 0.5
E4 | U-net-R VAT | 69.8 ± 8.3 | 65.8 ± 2.0 | 67.4 ± 2.8 | 48.6 ± 3.5 | 47.9 ± 1.1 | 48.2 ± 1.2 | 22.1 ± 3.1 | 21.7 ± 1.0 | 21.8 ± 2.0
E5 |  Multi-Inst (Wu et al., 2020) | 64.4 ± 9.4 | 71.8 ± 2.7 | 67.3 ± 4.1 | 43.5 ± 2.8 | 33.6 ± 0.6 | 37.9 ± 0.7 | 17.1 ± 2.5 | 13.2 ± 0.9 | 14.9 ± 1.5

##  5\. Applications

Our proposed semi-supervised framework allows for two important applications:
continual learning and knowledge transfer to unseen music genres. We will
discuss these two properties and their potential applications.

###  5.1. Continual Learning

The loss function of our proposed semi-supervised AMT framework contains a
supervised term $L_{\text{l}}$ and an unsupervised term $L_{\text{ul}}$. Even
when we encounter new unseen, unlabelled data, we can still use this new data
to minimize the unsupervised part of the model $L_{\text{ul}}$. That means,
the proposed model can be _retrained_ with any new data that was not collected
before. Therefore, our proposed framework is capable of improving itself via
new unlabelled data.

To confirm our framework’s ability of continual learning, we take the string
and woodwind subset of MusicNet as an example. We first train our models for
4,000 epochs (row 1 and 4 of Table 3, denoted as “4k”), and save the weights.
These weights are then used as starting weights when we train the model for
another 4,000 epochs with two different conditions: (1) without new data (row
2 and 5, denoted as “8k”); (2) using the test data as the unlabelled data as
well as the existing data (row 3 and 6, denoted as “4k + 4k”). For the string
subset of MusicNet, the model has already converged at 4,000 epochs,
additional supervised training does not change the performance much. When we
include the test data as the unlabelled data, it further pushes the accuracy
around 1 percentage point higher. The same goes for the woodwind dataset.
Although the improvement is relatively subtle at the moment, we plan to
investigate ways to further improve this in future research. This property
leads to the next application.

Figure 3. Transcribed piano rolls for J-pop. Blue notes indicate the main
melody; green notes indicate the accompaniment (piano and drums). The red
boxes indicate major differences in the piano rolls.

Our proposed semi-supervised framework.

###  5.2. Case Study: Transcribing Unseen Genres

In some cases, we have some labels in one data domain, while the target domain
we are interested in might not contain any labels at all. A model that can be
trained on one domain and its knowledge then transferred to the target domain
will be very useful. For example, we have some labelled data for classical
woodwind music, but we want our model to be able to transcribe clarinet covers
of Japanese pop music. Our proposed framework, as shown in Figure 3, is
capable of tackling this task.

We downloaded a few Japanese cover songs from YouTube, and we study the
transcription results produced by both the “woodwind 4k + 4k” model reported
in Table 3 and the best supervised baseline model (Wu et al., 2020) trained
for 8,000 epochs using only labelled data. Due to page limitations, we only
show one of the cover songs “Lemon” in Figure 3. More examples can be found in
the demo page provided as part of the supplementary
material222https://kinwaicheuk.github.io/ReconVAT. Since Japanese Pop music is
not included in the woodwind version of MusicNet data, the supervised baseline
model trained on only MusicNet produces a piano roll with a lot of missing
details such as the melody and the bass indicated by the red boxes. Training
the supervised model for more epochs does not help as the loss already
converged. Our proposed semi-supervised framework (ReconVAT) trained on both
labelled and unlabelled data tries to capture more details than the fully
supervised baseline model (Wu et al., 2020). For example, in the upper part of
the piano roll (Figure 3), the baseline model fails to capture the rhythmic
patterns that are only found in pop music. Moreover, there are also rhythmic
patterns for the piano accompaniment that are specific to pop music, and the
baseline model failed to transcribe these unseen piano patterns (middle and
lower part in Figure 3). One might argue that the transcription result for
ReconVAT is noisier in the bass region (bottom part of the piano roll). This
is due to the drum patterns in pop music. Since the labelled data in MusicNet
does not contain any drum beat as the accompaniment, the baseline model simply
ignores the drum sounds in the pop music. Our proposed model, however, is
aware of the presence of the drum beats by training with the unlabelled pop
music. It therefore attempts to transcribe the drum beats, making the
transcription slightly noisier than the baseline model. Nonetheless, this
example shows the success of our proposed model in transcribing unseen music
genres.

Table 3. Continual learning of the AMT model on the String and Woodwind subsets of MusicNet. Our proposed framework (4k+4k) has the ability to adapt to unseen and unlabeled new data to improve itself. | Frame | Note | Note w/ offset
---|---|---|---
String 4k | 68.4 ± 7.7 | 61.0 ± 13.8 | 41.6 ± 18.7
String 8k | 67.7 ± 8.0 | 61.1 ± 13.5 | 41.5 ± 18.8
String 4k+4k | 68.7 ± 8.0 | 62.7 ± 13.3 | 42.8 ± 18.9
Woodwind 4k | 67.4 ± 2.8 | 48.2 ± 1.2 | 21.8 ± 2.0
Woodwind 8k | 68.1 ± 2.8 | 50.9 ± 1.3 | 23.3 ± 3.2
Woodwind 4k+4k | 66.6 ± 0.4 | 51.7 ± 2.2 | 23.9 ± 4.6

##  6\. Discussion

Although VAT is found to be useful for our proposed ReconVAT, in our pilot
study we observed instability of VAT in some cases. More specifically, we
observed that VAT does not work well with some of the baseline models.
Whenever VAT is used, the transcription accuracy for the baseline model will
collapse to zero. Even when we pretrain the baseline model to first reach
their best performance, the moment the VAT kicks in, it causes a sudden
increase in the transcription loss after only one forward step and weight
update. The transcription loss does not decrease when the VAT component is
present. We discovered that the dropout layers are the culprit causing this
problem. Removing the dropout layers from the baseline models can prevent the
above-mentioned problem from happening, but at the same time, the
transcription accuracy for the baseline models are severely comprised without
the dropout layers. The dropout layers somehow cause instability of the
gradient $g$ (Equation (3)), making it change a lot during each iteration, and
it eventually leads to a vanishing gradient issue, and hence the gradient
explosion of the $\frac{g_{t}}{\lVert g_{t}\rVert}$ term. Although the models
proposed by Thickstun et al. (2017) and Pedersoli et al. (2020) do not have
any dropout layers, their models are too resources consuming and take too much
time to train. Therefore, we do not find enough motivation to apply VAT on
them.

The U-net model proposed by Cheuk et al. (2020) and Hung et al. (2019) does
not use any dropout layers, they are compact in size, and work well with our
proposed framework. However, we believe that
$p(Y_{\text{post}}|X_{\text{spec}},\theta)$ may be replaced by any type of
model as long as it does not affect the stability of the gradient $g$. Based
on these results, we believe that future research opportunities for AMT lie in
the semi-supervised or even unsupervised techniques that work well in
scenarios with insufficient labelled data instead of just exploring deep fully
supervised models that only work well with abundant labelled data.

##  7\. Conclusion

In this paper, we proposed a VAT based semi-supervised AMT framework,
ReconVAT, that works well for different kinds of musical instruments such as
strings and woodwinds. We demonstrated its power of leveraging unlabelled data
to enhance the transcription accuracy when the availability of labelled data
is limited. Our proposed framework also generalizes better to other genres
that are not present in the training dataset such as music covers of Japaneses
pop music. The compactness of our model also allows it to be easily deployed
in real-world applications22footnotemark: 2.

###### Acknowledgements.

This work is supported by A*STAR SING-2018-02-0204, MOE Tier 2 grant
MOE2018-T2-2-161, and SRG ISTD 2017 129.

## References

  * (1)
  * Amodei et al. (2016) Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, et al. 2016\.  Deep speech 2: End-to-end speech recognition in english and mandarin. In _International conference on machine learning_. PMLR, 173–182.
  * Bay et al. (2009) Mert Bay, Andreas F Ehmann, and J Stephen Downie. 2009\.  Evaluation of Multiple-F0 Estimation and Tracking Systems.. In _ISMIR_. 315–320.
  * Benetos et al. (2019) Emmanouil Benetos, Simon Dixon, Zhiyao Duan, and Sebastian Ewert. 2019.  Automatic Music Transcription: An Overview.  _IEEE Signal Processing Magazine_ 36 (2019), 20–30.
  * Benetos et al. (2013) Emmanouil Benetos, Simon Dixon, Dimitrios Giannoulis, Holger Kirchhoff, and Anssi Klapuri. 2013\.  Automatic music transcription: challenges and future directions.  _Journal of Intelligent Information Systems_ 41 (2013), 407–434.
  * Berg-Kirkpatrick et al. (2014) Taylor Berg-Kirkpatrick, Jacob Andreas, and Dan Klein. 2014\.  Unsupervised transcription of piano music. In _Advances in neural information processing systems_. 1538–1546.
  * Carvalho and Smaragdis (2017) Ralf Gunter Correa Carvalho and Paris Smaragdis. 2017.  Towards end-to-end polyphonic music transcription: Transforming music audio directly to a score. In _2017 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA)_. IEEE, 151–155.
  * Cemgil (2004) Ali Taylan Cemgil. 2004\.  _Bayesian music transcription_.  Ph.D. thesis, Radbound University Nijmegen Netherlands.
  * Chan et al. (2016) William Chan, Navdeep Jaitly, Quoc V. Le, and Oriol Vinyals. 2016.  Listen, attend and spell: A neural network for large vocabulary conversational speech recognition.  _2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ (2016), 4960–4964.
  * Chen and Chen (2001) Hung-Chen Chen and Arbee LP Chen. 2001.  A music recommendation system based on music data grouping and user interests. In _Proceedings of the tenth international conference on Information and knowledge management_. 231–238.
  * Chen et al. (2020) Luoxin Chen, Weitong Ruan, Xinyue Liu, and Jianhua Lu. 2020\.  SeqVAT: Virtual adversarial training for semi-supervised sequence labeling. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. 8801–8811.
  * Cheuk et al. (2020) K. W. Cheuk, H. Anderson, K. Agres, and D. Herremans. 2020.  nnAudio: An on-the-Fly GPU Audio to Spectrogram Conversion Toolbox Using 1D Convolutional Neural Networks.  _IEEE Access_ 8 (2020), 161981–162003.
  * Cheuk et al. (2020) Kin Wai Cheuk, Yin-Jyun Luo, Emmanouil Benetos, and Dorien Herremans. 2020.  The Effect of Spectrogram Reconstructions on Automatic Music Transcription:An Alternative Approach to Improve Transcription Accuracy. In _International Conference on Pattern Recognition (ICPR)_. IEEE, Washington, DC, USA, 9091–9098.
  * Cheuk et al. (2021) Kin Wai Cheuk, Yin-Jyun Luo, Emmanouil Benetos, and Dorien Herremans. 2021.  Revisiting the Onsets and Frames Model with Additive Attention. In _Proceedings of the International Joint Conference on Neural Networks_. IEEE, In press.  https://doi.org/10.1109/SPW.2018.00014
  * Choi and Cho (2019) Keunwoo Choi and Kyunghyun Cho. 2019.  Deep Unsupervised Drum Transcription. In _ISMIR_ , Arthur Flexer, Geoffroy Peeters, Julián Urbano, and Anja Volk (Eds.). 183–191.  http://archives.ismir.net/ismir2019/paper/000020.pdf
  * Cuthbert and Ariza (2010) Michael Scott Cuthbert and Christopher Ariza. 2010.  music21: A toolkit for computer-aided musicology and symbolic music data. In _ISMIR_.
  * Emiya et al. (2010) Valentin Emiya, Nancy Bertin, Bertrand David, and Roland Badeau. 2010.  MAPS-A piano database for multipitch estimation and automatic transcription of music.  _Hal Inria_ (2010).
  * Goodfellow et al. (2015) Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015\.  Explaining and Harnessing Adversarial Examples. In _International Conference on Learning Representations_.
  * Hawthorne et al. (2017) Curtis Hawthorne, Erich Elsen, Jialin Song, Adam Roberts, Ian Simon, Colin Raffel, Jesse Engel, Sageev Oore, and Douglas Eck. 2017.  Onsets and Frames: Dual-Objective Piano Transcription. In _ISMIR_.
  * Hawthorne et al. (2019) Curtis Hawthorne, Andriy Stasyuk, Adam Roberts, Ian Simon, Cheng-Zhi Anna Huang, Sander Dieleman, Erich Elsen, Jesse Engel, and Douglas Eck. 2019.  Enabling Factorized Piano Music Modeling and Generation with the MAESTRO Dataset. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=r1lYRjC9F7
  * Huang and Yang (2020) Yu-Siang Huang and Yi-Hsuan Yang. 2020.  Pop Music Transformer: Generating Music with Rhythm and Harmony.  _arXiv preprint arXiv:2002.00212_ (2020).
  * Hung et al. (2019) Yun-Ning Hung, I Ping Chiang, Yian Chen, and Yi-Hsuan Yang. 2019\.  Musical Composition Style Transfer via Disentangled Timbre Representations. In _IJCAI_. 4697–4703.
  * Jiang and Dannenberg (2019) Zheng Jiang and Roger B Dannenberg. 2019.  Melody identification in standard midi files. In _Proceedings of the 16th sound & music computing conference_. 65–71.
  * Kelz et al. (2019) Rainer Kelz, Sebastian Böck, and Gerhard Widmer. 2019\.  Deep polyphonic adsr piano note transcription. In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 246–250.
  * Kim and Bello (2019) Jong Wook Kim and Juan Pablo Bello. 2019.  Adversarial Learning for Improved Onsets and Frames Music Transcription.  _International Society forMusic Information Retrieval Conference_ (2019), 670–677.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kong et al. (2020) Qiuqiang Kong, Keunwoo Choi, and Yuxuan Wang. 2020.  Large-Scale MIDI-based Composer Classification.  _arXiv preprint arXiv:2010.14805_ (2020).
  * Kreyssig and Woodland (2020) Florian L Kreyssig and Philip C Woodland. 2020.  Cosine-distance virtual adversarial training for semi-supervised speaker-discriminative acoustic embeddings.  _Interspeech_ (2020).
  * Kuwahara et al. (2019) Toyoaki Kuwahara, Yuichi Sei, Yasuyuki Tahara, Ryohei Orihara, and Akihiko Ohsuga. 2019.  Model Smoothing Using Virtual Adversarial Training for Speech Emotion Estimation. In _2019 IEEE International Conference on Big Data, Cloud Computing, Data Science & Engineering (BCD)_. IEEE, 60–64.
  * Lin et al. (2017) Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. 2017.  Focal loss for dense object detection. In _Proceedings of the IEEE international conference on computer vision_. 2980–2988.
  * Liumei et al. (2021) Zhang Liumei, Jiang Fanzhi, Li Jiao, Ma Gang, and Liu Tianshi. 2021.  K-means clustering analysis of Chinese traditional folk music based on midi music textualization. In _2021 6th International Conference on Intelligent Computing and Signal Processing (ICSP)_. IEEE, 1062–1066.
  * Magalhaes (2015) José Pedro Magalhaes. 2015\.  CHORDIFY: THREE YEARS AFTER THE LAUNCH. In _ISMIR_.
  * Meroño-Peñuela et al. (2017) Albert Meroño-Peñuela, Rinke Hoekstra, Aldo Gangemi, Peter Bloem, Reinier de Valk, Bas Stringer, Berit Janssen, Victor de Boer, Alo Allik, Stefan Schlobach, et al. 2017\.  The MIDI linked data cloud. In _International Semantic Web Conference_. Springer, 156–164.
  * Miyato et al. (2016) Takeru Miyato, Andrew M Dai, and Ian Goodfellow. 2016\.  Adversarial training methods for semi-supervised text classification.  _ICLR_ (2016).
  * Miyato et al. (2019) T. Miyato, S. Maeda, M. Koyama, and S. Ishii. 2019\.  Virtual Adversarial Training: A Regularization Method for Supervised and Semi-Supervised Learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 41, 8 (2019), 1979–1993.  https://doi.org/10.1109/TPAMI.2018.2858821
  * Park and Chang (2019) Dae Hoon Park and Yi Chang. 2019.  Adversarial sampling and training for semi-supervised information retrieval. In _The World Wide Web Conference_. 1443–1453.
  * Pedersoli et al. (2020) Fabrizio Pedersoli, George Tzanetakis, and Kwang Moo Yi. 2020\.  Improving Music Transcription by Pre-Stacking A U-Net. In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 506–510.
  * Ramachandran et al. (2019) Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jon Shlens. 2019\.  Stand-Alone Self-Attention in Vision Models. In _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2019/file/3416a75f4cea9109507cacd8e2f2aefc-Paper.pdf
  * Román et al. (2018) Miguel A. Román, Antonio Pertusa, and Jorge Calvo-Zaragoza. 2018.  An End-to-end Framework for Audio-to-Score Music Transcription on Monophonic Excerpts.. In _ISMIR_. 34–41.
  * Román et al. (2019) Miguel A. Román, Antonio Pertusa, and Jorge Calvo-Zaragoza. 2019.  A Holistic Approach to Polyphonic Music Transcription with Neural Networks. In _ISMIR_. 731–737.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018\.  Self-Attention with Relative Position Representations. In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_. Association for Computational Linguistics, New Orleans, Louisiana, 464–468.  https://doi.org/10.18653/v1/N18-2074
  * Sigtia et al. (2015) Siddharth Sigtia, Emmanouil Benetos, and Simon Dixon. 2015\.  An End-to-End Neural Network for Polyphonic Piano Music Transcription.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 24 (2015), 927–939.
  * Sun and Lee (2017) JQ Sun and Seok-Pil Lee. 2017.  Query by singing/humming system based on deep learning.  _Int. J. Appl. Eng. Res_ 12, 13 (2017), 973–4562.
  * Thickstun et al. (2017) John Thickstun, Zaïd Harchaoui, Dean P. Foster, and Sham M. Kakade. 2017.  Invariances and Data Augmentation for Supervised Music Transcription.  _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ (2017), 2241–2245.
  * Thickstun et al. (2016) John Thickstun, Zaïd Harchaoui, and Sham M. Kakade. 2016\.  Learning Features of Music From Scratch. In _ICLR_ , Vol. abs/1611.09827.
  * Won et al. (2019) Minz Won, Sanghyuk Chun, and Xavier Serra. 2019.  Toward Interpretable Music Tagging with Self-Attention.  arXiv:1906.04972 [cs.SD]
  * Wu et al. (2019) Yu-Te Wu, Berlin Chen, and Li Su. 2019.  Polyphonic Music Transcription with Semantic Segmentation. In _ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. 166–170.  https://doi.org/10.1109/ICASSP.2019.8682605
  * Wu et al. (2020) Y. T. Wu, B. Chen, and L. Su. 2020.  Multi-Instrument Automatic Music Transcription With Self-Attention-Based Instance Segmentation.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 28 (2020), 2796–2809.  https://doi.org/10.1109/TASLP.2020.3030482
  * Yamaguchi and Fukumoto (2019) Genki Yamaguchi and Makoto Fukumoto. 2019.  A music recommendation system based on melody creation by interactive GA. In _2019 20th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)_. IEEE, 286–290.


# Coloured and Dependent Planar Matchings of Random Bipartite Graphs

Ghurumuruhan Ganesan1
1IISER, Bhopal E-mail<EMAIL_ADDRESS>
Abstract: In this paper, we study two problems related to planar matchings in
random bipartite graphs. First, we colour each edge of the complete bipartite
graph $K_{n,n}$ uniformly randomly from amongst $r$ colours and show that if
$r$ grows linearly with $n,$ then the maximum rainbow matching is a non-
trivial fraction of $r,$ with high probability, i.e. with probability
converging to one as $n\rightarrow\infty.$ Next we consider planar matchings
in a dependent setting where each vertex is forced to choose exactly one
neighbour from amongst all possible choices. We obtain estimates for the
largest size of a planar matching and also discuss the implication of our
results to longest increasing subsequences in enlarged random permutations.
Keywords: Rainbow Planar Matchings, Dependent Planar Matchings, Random
Bipartite Graphs.
2010 Mathematics Subject Classification: Primary: 60J10, 60K35; Secondary:
60C05, 62E10, 90B15, 91D30.

##  1 Introduction

Planar matchings in random graphs have applications in determining longest
length of increasing subsequences in permutations and related topics. In [8,
6, 7] the authors studied various properties of the largest size of a planar
matching in random bipartite graphs with dependencies. In the first part of
the paper, we study _rainbow planar matchings_ of randomly coloured bipartite
graphs. Specifically, we colour each edge of the complete bipartite graph with
a random colour and use martingale difference methods and segmentation to
obtain deviation bounds on the maximum size of a rainbow planar matching.

In the second part of our paper, we study dependent planar matchings of random
bipartite graphs with applications to enlarged random permutations. Random
permutations are of great interest from both theoretical and application
perspectives. In particular, the longest increasing subsequence $M_{n}$ of a
uniformly randomly chosen permutation of $\\{1,2,\ldots,n\\}$ has been well-
studied and various properties of $M_{n}$ are known. The paper [10] initiated
the study of the longest increasing subsequence of a randomly chosen
permutation and [4] used subadditive methods to show that the expected value
of $\frac{M_{n}}{\sqrt{n}}$ converges to a constant $c.$ That $c=2$ was
independently determined in [11] and [5]. Later [1] comprehensively determined
the asymptotics of $M_{n}$ including a central limit theorem and for a
detailed survey, we refer to [9].

In this paper, we consider a variant of uniform permutations which we call as
enlarged permutations. Roughly speaking, we increase the “alphabet size” of
the $n-$tuples to $k\geq n$ and study the deviation and expectation properties
of the longest increasing subsequence $T_{n}=T_{n}(k).$ The change in the
alphabet size affects the underlying distribution due to an increase in size
of the sample space and we use a segmentation approach to obtain the desired
bounds for $T_{n}.$ Throughout, for completeness, we state and prove our
results in the form of planar matchings.

The paper is organized as follows: In Section 2, we state and prove our main
result regarding the maximum size of rainbow planar matchings and in Section
3, we state and prove our main result regarding the maximum size of dependent
planar matchings and describe how our result applies to enlarged random
permutations.

##  2 Rainbow Planar Matchings

For $i\geq 1,$ let $u_{i}=(i,0)_{2}$ and $v_{i}=(i,1)_{2}$ be points in
$\mathbb{R}^{2}.$ We use the subscript $2$ to differentiate from the two-tuple
notations for edges introduced later. For each $i\neq j$ join the vertices
$u_{i}$ and $v_{j}$ by an edge to obtain an infinite bipartite graph
$K_{tot}.$ For integer $n\geq 1$ let $K_{n,n}$ be the complete bipartite graph
containing $n$ bottom vertices $X=\\{u_{1},\ldots,u_{n}\\}$ and $n$ top
vertices $Y=\\{v_{1},\ldots,v_{n}\\}.$ This is illustrated in Figure 1 where
$S$ denotes the line $x=1$ that contains the vertices of $Y$ and $T$ denotes
the line $x=0$ that contains the vertices of $X.$

An edge $e\in K_{n,n}$ if and only if $e$ has one end-vertex $u_{i}\in X$ and
the other end-vertex $v_{j}\in Y.$ We denote the edge $e$ as
$e=(u_{i},v_{j}).$ A _matching_ of size $t$ in $K_{n,n}$ is a set of vertex
disjoint edges ${\cal W}=\\{e_{1},\ldots,e_{t}\\}.$ Suppose $e_{i}$ has end-
vertices $a_{l}=(u_{i_{l}},1)_{2}\in X$ and $b_{l}=(v_{j_{l}},0)_{2}\in Y.$ We
say that ${\cal W}$ is a _planar matching_ if $i_{1}<i_{2}<\ldots<i_{t}$ and
$j_{1}<j_{2}<\ldots<j_{t}.$ In other words, no two edges in ${\cal W}$
intersect each other. The size of ${\cal W}$ is defined to the number of edges
$t.$

In Figure 1, we illustrate the above definition with an example of a planar
matching ${\cal W}_{0}$ containing six edges
$(u_{1},v_{2}),(u_{4},v_{3}),(u_{5},v_{5}),(u_{7},v_{6})$ and $(u_{9},v_{7}).$

Figure 1: Illustration of a planar matching.

Each edge $f$ of $K_{n,n}$ is now coloured with a colour $X_{f}$ chosen
uniformly randomly from the set $\\{1,2,\ldots,r\\},$ independent of other
edges. Let $G$ be the resulting randomly coloured graph and let ${\cal
W}=\\{h_{1},h_{2},\ldots,h_{t}\\}$ be a planar matching of $G$ containing $t$
edges.

######  Definition 2.1.

We say that ${\cal W}$ is a _rainbow_ planar matching if $X_{h_{i}}\neq
X_{h_{j}}$ for any $h_{i}\neq h_{j}.$

In other words, all the colours in ${\cal W}$ must be distinct.

Letting $R_{n}$ denote the maximum size of a rainbow planar matching of $G,$
we have the following result.

######  Theorem 2.2.

Let $r=\alpha n$ for some $\alpha>0.$ There exists $0<\alpha_{0}<1$ such that
for every $\alpha>\alpha_{0},$ there are constants
$0<\beta_{1}\leq\beta_{2}<1$ strictly and $\beta_{3}>0$ such that

$\mathbb{P}\left(\beta_{1}r\leq R_{n}\leq\beta_{2}r\right)\geq
1-e^{-\beta_{3}n}\text{ and }\beta_{1}r\leq\mathbb{E}R_{n}\leq\beta_{2}r.$
(2.1)

Moreover, $var(R_{n})\leq 2\mathbb{E}R_{n}.$

In words, the above result says that the largest size of the rainbow planar
matching is a non-trivial fraction of the total number of colours $r,$ if the
parameter $\alpha$ is close to $1.$ On the other hand, the proof of our result
can be also adapted to show that if $r=o(n),$ then
$\frac{R_{n}}{r}\longrightarrow 1$ in probability as $n\rightarrow\infty.$
This hints at the possibility of a transition point for the size of the
rainbow planar matching, with respect to the parameter $\alpha.$

_Proof Theorem 2.2_: The proof of the variance bound uses a pivotal edge
argument and is exactly as in the strong matching case (see proof of Theorem
$2.2,$ [3]). Next we show that the expectation bounds follow from the
deviation bounds. Indeed from the deviation lower bound in (2.1), we get
$\mathbb{E}R_{n}\geq\beta_{1}r(1-e^{-\beta_{3}n})$ and using the fact that
$R_{n}\leq r$ and the upper bound in (2.1), we get that
$\mathbb{E}R_{n}\leq\beta_{2}r+re^{-\beta_{3}n}.$ This obtains the expectation
bounds in (2.1).

We now begin with the proof of the upper deviation bound in (2.1). Let ${\cal
S}=\\{(u_{i},v_{i})\\}_{1\leq i\leq t}$ be any planar matching containing $t$
edges. The probability that ${\cal S}$ is a rainbow planar matching is
$\prod_{i=1}^{t-1}\left(\frac{r-i}{r}\right)$ which is bounded above by

$\displaystyle\exp\left(-\frac{1}{r}\sum_{i=1}^{t-1}i\right)$ $\displaystyle=$
$\displaystyle\exp\left(-\frac{t(t-1)}{2r}\right)$ $\displaystyle=$
$\displaystyle\exp\left(\frac{t}{2r}\right)\exp\left(-\frac{t^{2}}{2r}\right)$
$\displaystyle\leq$ $\displaystyle\sqrt{e}\exp\left(-\frac{t^{2}}{2r}\right),$

since $t\leq r.$ The number of choices for $\\{u_{i}\\}_{1\leq i\leq t}$ is
${n\choose t}$ and an analogous bound holds for $\\{v_{i}\\}_{1\leq i\leq t}.$
Therefore if $F_{n}=F_{n}(\epsilon),\epsilon<\frac{1}{2}$ denotes the event
that every rainbow planar matching has size at most $(1-\epsilon)r,$ then by
the union bound we have that

$\mathbb{P}(F_{n}^{c})\leq\sqrt{e}\sum_{t\geq(1-\epsilon)r+1}{n\choose
t}^{2}\cdot\exp\left(-\frac{t^{2}}{2r}\right)\leq\sqrt{e}\sum_{t\geq(1-\epsilon)r+1}{n\choose
t}^{2}e^{-(1-\epsilon)^{2}r/2}.$ (2.2)

Assuming $\alpha>\frac{1}{2},$ we choose $\epsilon>0$ small enough to apply
the monotonicity of the Binomial coefficient and the Stirling approximation
successively to get that ${n\choose t}\leq{n\choose(1-\epsilon)r}\leq
ne^{nH((1-\epsilon)\alpha)}$ where $H(x)=-x\log{x}-(1-x)\log(1-x)$ is the
binary entropy function and the logarithms are natural throughout. From (2.2)
we therefore get that

$\mathbb{P}(F_{n}^{c})\leq\sqrt{e}\sum_{t\geq(1-\epsilon)r+1}n^{2}e^{2nH((1-\epsilon)\alpha)}e^{-(1-\epsilon)^{2}\alpha
n/2}.$ (2.3)

We know that $H(x)\longrightarrow 0$ as $x\rightarrow 0.$ Therefore if
$\alpha_{0}$ is the solution to the equation $2H(x)=\frac{x}{2},$ then for
every $\alpha>\alpha_{0},$ we can choose $\epsilon>0$ small in (2.3) to get
that $\mathbb{P}(F_{n}^{c})\leq e^{-\delta n}$ for some constant $\delta>0.$
Fixing such an $\epsilon,$ gives the upper deviation bound in (2.1).

For the lower deviation bound in (2.1), we argue as follows: For
$0<\epsilon<\frac{1}{2},$ let $E_{n}$ be the event that the maximum rainbow
planar matching contains $t\leq\epsilon r$ edges. We bound $\mathbb{P}(E_{n})$
by estimating the size of the colour set of the $n$ vertical edges
$f_{i}=(u_{i},v_{i}),1\leq i\leq n.$ The probability that the colour
$X_{f_{i}}$ of the edge $f_{i}$ belongs to the set $\\{1,2,\ldots,t\\}$ equals
$\frac{t}{r}\leq\epsilon.$ Therefore the probability that each $f_{i},1\leq
i\leq n$ is coloured with a colour from $\\{1,2,\ldots,t\\}$ is at most
$\epsilon^{n}.$ Since there are ${r\choose t}\leq{r\choose\epsilon r}\leq
2^{r}=2^{\alpha n}$ ways of choosing $t$ colours from the set of all available
colours, we get by the union bound that

$\mathbb{P}(E_{n})\leq\sum_{1\leq t\leq\epsilon r}2^{\alpha n}\epsilon^{n}\leq
n(2^{\alpha}\epsilon)^{n}\leq e^{-\gamma n}$

for some constant $\gamma>0$ provided $\epsilon>0$ is small enough. Fixing
such an $\epsilon,$ we get the lower deviation bound in (2.1).

##  3 Dependent Planar Matchings

Let $K_{tot}$ be the infinite bipartite graph described in Section 2 and for
integers $k\geq n\geq 1,$ let $K_{k,n}\subseteq K_{tot}$ be the complete
bipartite graph containing the $k$ top vertices $v_{1},\ldots,v_{k}$ and the
$n$ bottom vertices $u_{1},\ldots,u_{n}.$ Let ${\cal G}_{k,n}$ be the set of
all $1-$regular subgraphs of $K_{k,n};$ i.e., the set of all subgraphs of
$K_{k,n}$ satisfying the property that each bottom vertex $u_{i},1\leq i\leq
n$ is adjacent to exactly one top vertex $v_{j},1\leq j\leq k$ and each top
vertex is adjacent to at most one bottom vertex. Let $G$ be uniformly randomly
chosen from ${\cal G}_{k,n}$ and let $T_{n}=T_{n}(k)$ be the largest size of a
planar matching of $G.$

For $k=n,$ the quantity $T_{n}$ could be interpreted as the length of the
longest increasing subsequence in a uniformly randomly chosen permutation of
$n.$ In this case, it is well-known that $T_{n}$ is of the order of $\sqrt{n}$
with high probability [9], i.e. with probability converging to one as
$n\rightarrow\infty.$ We could therefore think of the above dependent planar
matching setup as an “enlarged permutation” where we choose $n-$tuples with
distinct entries from the set $\\{1,2,\ldots,k\\}$ with $k\geq n.$

For general $k\geq n,$ we have the following result regarding the mean and
variance of $T_{n}.$ As before, constants do not depend on $n.$

######  Theorem 3.1.

We have:
$(a)$ For every $\epsilon>0,$ there are positive constants $C_{i},0\leq i\leq
3$ and a constant $0<D_{0}<1$ such that for all $n\geq C_{0},$

$\mu_{low}:=(1-e^{-1})\sqrt{n}-\frac{17}{\sqrt{n}}\leq\mathbb{E}T_{n}\leq(e+\epsilon)\sqrt{n}+1=:\mu_{up},$
(3.1) $\mathbb{P}\left(T_{n}\leq\mu_{up}\right)\geq 1-e^{-C_{1}\sqrt{n}}\text{
and }\mathbb{P}\left(T_{n}\geq(1-\epsilon)\mu_{low}\right)\geq 1-z_{n},$ (3.2)

where $z_{n}:=\min\left(D_{0},\frac{C_{2}}{\sqrt{n}}+\frac{C_{2}n}{k}\right).$
$(b)$ For every $2<b=b(n)\leq\frac{n}{(32)^{2}\log{n}}$ we have that

$\mathbb{P}\left(T_{n}\geq\sqrt{\frac{n}{b\log{n}}}\right)\geq
1-\exp\left(-\left(\frac{b}{2}-1\right)\log{n}\right).$ (3.3)

From (3.2) we see that if $k$ grows faster than $n,$ then the maximum planar
matching size $T_{n}$ is of the order of $\sqrt{n}$ with high probability,
i.e. with probability converging to one as $n\rightarrow\infty.$

The proof of the upper bounds in Theorem 3.1 is analogous to the case of
random permutations (see Lemma $1.5$ in Romik (2014)). For completeness, we
give small proofs in the next section. In our proof of the lower deviation
bounds in Theorem 3.1, we use segmentation to split the given graph $K_{k,n}$
into smaller subgraphs and use planar matchings within the smaller subgraphs
to obtain an estimate on the overall quantity $T_{n}.$ Therefore, in the next
subsection, we collect preliminary results regarding the minimum size of a
segmented planar matching of $K_{k,n}$ and independent planar matchings,
respectively. In the final subsection, we prove Theorem 3.1.

### Segmented Planar Matchings

For integer $1\leq t\leq n$ and for $1\leq i\leq I:=\frac{n}{t}$ let ${\cal
T}_{i}$ be the set of all integers $l$ satisfying $(i-1)t+1\leq l\leq it.$ For
simplicity we have assumed that $\frac{n}{t}$ is an integer; if not then we
let $I$ be the largest integer such that $I\cdot t\leq n$ and allow the last
“segment” ${\cal T}_{I}$ to be the set of all integers $j$ satisfying
$(I-1)t+1\leq i\leq n.$ In this case, ${\cal T}_{I}$ contains between
$\frac{n}{t}$ and $\frac{2n}{t}$ integers. Similarly for an integer $1\leq
s\leq k$ and for $1\leq j\leq J:=\frac{k}{s}$ let ${\cal S}_{i}$ be the set of
all integers $l$ satisfying $(j-1)s+1\leq l\leq js.$ As before, we assume that
$\frac{k}{s}$ is an integer and we always choose $s\leq\frac{tk}{n}$ so that
the number of “bottom” segments $I\leq J,$ the number of “top” segments.

Suppose $s=\frac{tk}{n}$ so that $I=J$ and let ${\cal W}$ be a planar matching
of $G.$ We say that ${\cal W}$ is a $t-$segmented planar matching if for each
edge $e\in{\cal W},$ there exists an integer $1\leq i\leq I$ such that one
end-vertex of $e$ belongs to ${\cal T}_{i}$ and the other end-vertex of $e$
belongs to ${\cal S}_{i}.$ For $1\leq i\leq\frac{n}{t},$ let $A_{i}$ be the
event that there exists an integer $z\in{\cal T}_{i}$ such that
$\pi(z)\in{\cal S}_{i}.$ Defining the _minimum size_ of a $t-$segmented planar
matching of the random graph $G$ to be

$X_{t}=X_{t}(s):=\sum_{i=1}^{n/t}1{1}(A_{i}),$ (3.4)

we have the following estimates for the mean and variance of $X_{t}.$

######  Lemma 3.1.

Suppose $s=\frac{kt}{n}$ so that $I=J.$ Letting
$\mu_{t}:=\frac{n}{t}\left(1-\exp\left(-\frac{t^{2}}{n}\right)\right),$ we
have that

$\mu_{t}-\frac{17}{t}e^{-\frac{t^{2}}{n}}\leq\mathbb{E}X_{t}\leq\mu_{t}+\frac{32n}{k^{2}}e^{-\frac{t^{2}}{n}}.$
(3.5)

If $\theta_{1}\sqrt{n}\leq t\leq\theta_{2}\sqrt{n}$ for some constants
$\theta_{1},\theta_{2}>0,$ then there exists a positive constant
$D=D(\theta_{1},\theta_{2})$ such that

$var(X_{t})\leq D\left(\sqrt{n}+\frac{n^{2}}{k}\right)$ (3.6)

In the proof of Theorem 3.1 in the next Section, we use the fact that $X_{t}$
is a lower bound on $T_{n}$ to obtain deviation and expectation estimates for
$T_{n}.$

_Proof of ( 3.5) in Lemma 3.1_: We use Lemma 4.2 in Appendix with
$s=\frac{kt}{n}$ to get from the upper bound in (A.2) that

$\mathbb{P}(A_{1}^{c})\leq\exp\left(-\frac{t^{2}}{n}+\frac{4(s+t)^{2}t}{k^{2}}\right).$

The term

$\frac{(s+t)^{2}t}{k^{2}}=\frac{(k+n)^{2}t}{k^{2}n^{2}}\leq\frac{4t}{n^{2}}\leq\frac{4}{n}$
(3.7)

where the first inequality in (3.7) is true since $k\geq n$ and the second
inequality in (3.7) follows from the fact that $t\leq n.$ Thus

$\mathbb{P}(A_{1}^{c})\leq\exp\left(-\frac{t^{2}}{n}+\frac{16}{n}\right)\leq\exp\left(-\frac{t^{2}}{n}\right)\left(1+\frac{17}{n}\right)$
(3.8)

for all $n$ large and so

$\mathbb{E}X_{t}=\frac{n}{t}\left(1-\mathbb{P}(A_{1}^{c})\right)\geq\frac{n}{t}\left(1-\exp\left(-\frac{t^{2}}{n}\right)\right)-\frac{17}{t}e^{-\frac{t^{2}}{n}}.$

This obtains the lower bound in (3.5).

Similarly using the lower bound in (A.2) we get that

$\mathbb{P}(A_{1}^{c})\geq\exp\left(-\frac{t^{2}}{n}-\frac{8(s+t)^{2}t}{k^{2}}\right),$

where
$\frac{(s+t)^{2}t}{k^{2}}=\frac{(k+n)^{2}t}{k^{2}n^{2}}\geq\frac{4t}{k^{2}}$
since $k\geq n.$ Thus

$\mathbb{P}(A_{1}^{c})\geq\exp\left(-\frac{t^{2}}{n}\right)\exp\left(-\frac{32t}{k^{2}}\right)\geq\exp\left(-\frac{t^{2}}{n}\right)\left(1-\frac{32t}{k^{2}}\right)$

and consequently,

$\mathbb{E}X_{t}=\frac{n}{t}\left(1-\mathbb{P}(A_{1}^{c})\right)\leq\frac{n}{t}\left(1-\exp\left(-\frac{t^{2}}{n}\right)\right)+\frac{32n}{k^{2}}e^{-\frac{t^{2}}{n}}.$

This obtains the upper bound in (3.5).

_Proof of ( 3.6) in Lemma 3.1_: To obtain the deviation estimate for $X_{t},$
we let $Y=\frac{n}{t}-X_{t}$ and first estimate the variance of $Y.$ Setting

$cov(1{1}(A_{i}^{c}),1{1}(A_{j}^{c})):=\mathbb{P}(A_{i}^{c}\cap
A_{j}^{c})-\mathbb{P}(A_{i}^{c})\mathbb{P}(A_{j}^{c})$

to be the covariance between the indicator functions of the events $A_{i}$ and
$A_{j},$ we have that

$\displaystyle var(Y)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n/t}\mathbb{P}(A^{c}_{i})-\mathbb{P}^{2}(A^{c}_{i})+2\sum_{i<j}cov(1{1}(A_{i}^{c}),1{1}(A_{j}^{c}))$
(3.9) $\displaystyle\leq$
$\displaystyle\frac{n}{t}\left(\mathbb{P}(A^{c}_{1})-\mathbb{P}^{2}(A^{c}_{1})\right)+\frac{2n^{2}}{t^{2}}cov(1{1}(A_{1}^{c}),1{1}(A_{2}^{c}))$
$\displaystyle\leq$
$\displaystyle\frac{n}{t}\mathbb{P}(A^{c}_{1})+\frac{2n^{2}}{t^{2}}cov(1{1}(A_{1}^{c}),1{1}(A_{2}^{c}))$
$\displaystyle\leq$
$\displaystyle\frac{2n}{t}e^{-\frac{t^{2}}{n}}+\frac{2n^{2}}{t^{2}}cov(1{1}(A_{1}^{c}),1{1}(A_{2}^{c}))$

for all $n$ large, using (3.8).

For the second term in (3.9), we use the correlation estimate (A.3) in Lemma
4.2 to get that

$cov(1{1}(A_{1}^{c}),1{1}(A_{2}^{c}))\leq\mathbb{P}(A_{1}^{c})\mathbb{P}(A_{2}^{c})\left(e^{\frac{5t^{2}}{k}}-1\right).$

Since $t\leq\theta_{2}\sqrt{n},$ we have that
$\frac{5t^{2}}{k}\leq\frac{5\theta_{2}^{2}n}{k}\leq 5\theta_{2}^{2}.$ For all
$x\leq 5\theta_{2}^{2},$ we have that $e^{x}\leq 1+D_{1}x$ for some large
constant $D_{1}>0$ and so again using $\theta_{1}\sqrt{n}\leq
t\leq\theta_{2}\sqrt{n},$ we get that

$cov(1{1}(A_{1}^{c}),1{1}(A_{2}^{c}))\leq
5D_{1}\frac{t^{2}}{k}\mathbb{P}(A_{1}^{c})\mathbb{P}(A_{2}^{c})\leq\frac{D_{2}n}{k}e^{-\frac{2t^{2}}{n}}\leq\frac{D_{3}n}{k}$
(3.10)

for some constants $D_{2},D_{3}>0.$ Plugging (3.10) into (3.9) and using
$\theta_{1}\sqrt{n}\leq t\leq\theta_{2}\sqrt{n},$ we get that

$var(Y)\leq\frac{2n}{t}e^{-\frac{t^{2}}{n}}+\frac{n^{2}}{t^{2}}\cdot\frac{D_{3}n}{k}\leq
D_{4}\left(\sqrt{n}+\frac{n^{2}}{k}\right)$

for some constant $D_{4}>0.$ Since $var(X_{t})=var(Y),$ this completes the
proof of (3.6).

### Proof of Theorem 3.1

_Proof of the upper bound in ( 3.1)_: For a given integer $l\geq 1$ we first
estimate the probability of the event $E_{l}$ that the random graph $G$
contains a planar matching of size $l.$ Indeed, let $\pi(i)$ be the
$x-$coordinate of the top vertex adjacent to the bottom vertex $u_{i}$ in the
graph $G$ and suppose that $\pi({i_{1}})<\ldots<\pi(i_{l})$ for some
deterministic integers $1\leq i_{1}<i_{2}<\ldots<i_{l}\leq n.$ The number of
choices for $\\{i_{1},\ldots,i_{l}\\}$ is ${n\choose l}$ and the number of
choices for $\\{\pi({i_{1}}),\ldots,\pi({i_{l}})\\}$ is ${k\choose l}.$ From
(A.4) and the union bound, we then get that

$\mathbb{P}(E_{l})\leq{n\choose l}\cdot{k\choose
l}\cdot\frac{1}{k(k-1)\ldots(k-l+1)}={n\choose l}\cdot\frac{1}{l!}.$

Using ${n\choose l}\leq\left(\frac{ne}{l}\right)^{l}$ and $l!\geq
l^{l}e^{-l},$ we get that
$\mathbb{P}(E_{l})\leq\left(\frac{ne^{2}}{l^{2}}\right)^{l}\leq\left(\frac{e}{a}\right)^{2l}$
for $l\geq a\sqrt{n}.$

If $a>e$ strictly then $\left(\frac{e}{a}\right)^{2l}=e^{-2\delta l}$ for some
constant $\delta>0$ and so
$\mathbb{P}(E_{l})\leq e^{-2\delta l}.$ If $E_{up}$ denotes the event that $G$
contains a planar matching of length at least $a\sqrt{n},$ then from the union
bound, we get that

$\mathbb{P}(E_{up})\leq n\cdot e^{-2a\delta\sqrt{n}}\leq e^{-a\delta\sqrt{n}}$
(3.11)

for all $n$ large. To upper bound the expectation, we use the fact that if
$E_{up}$ occurs, then $T_{n}\leq a\sqrt{n}$ and if the complement event
$E_{up}^{c}$ occurs, then $T_{n}\leq n.$ Therefore from (3.11), we get that
$\mathbb{E}T_{n}\leq a\sqrt{n}+n\cdot e^{-a\delta\sqrt{n}}\leq a\sqrt{n}+1$
for all $n$ large. This obtains the upper bound in (3.1).

_Proof of the lower bound in ( 3.1)_: By definition the term $X_{t}$ defined
in (3.4) is a lower bound on the maximum size $T_{n}$ of a planar matching of
$G.$ To see this is true suppose $X=w$ and suppose
$A_{j_{1}},\ldots,A_{j_{w}}$ occur with $j_{1}<\ldots<j_{w}.$ For each $1\leq
u\leq w,$ there exists an index $p_{u}\in{\cal T}_{j_{u}}$ and an integer
$q_{u}\in{\cal S}_{j_{u}}$ such that $\pi(p_{u})=q_{u}.$ By definition
$\pi(p_{1})<\pi(p_{2})<\ldots<\pi(p_{w})$ and so $G$ contains a planar
matching of size at least $w.$

We therefore use Lemma 3.1 with $t=\sqrt{n}$ to get that
$\mu_{t}=\sqrt{n}(1-e^{-1})$ and so from the lower bound in (3.5), we get that
$\mathbb{E}X_{t}\geq(1-e^{-1})\sqrt{n}-\frac{17}{\sqrt{n}}.$ This completes
the proof of the lower bound in (3.1).

_Proof of ( 3.2)_: The upper bound follows from (3.11). To prove the lower
bound, we use Lemma 3.1 with $t=\sqrt{n}.$ First from the upper bound in (3.5)
and the fact that $k\geq n,$ we get that

$\mathbb{E}X_{t}\leq(1-e^{-1})\sqrt{n}+\frac{32n}{k^{2}}\leq(1-e^{-1})\sqrt{n}+\frac{32}{n}\leq\sqrt{n}.$

From the variance estimate (3.6), we already know that

$var(X_{t})\leq D\left(\sqrt{n}+\frac{n^{2}}{k}\right).$ (3.12)

We now use the Paley-Zygmund inequality to show that
$X_{t}\geq(1-\epsilon)\mu_{low}$ with positive probability and then use the
fact that $X_{t}$ is a lower bound for $T_{n}$ to get that
$T_{n}\geq(1-\epsilon)\mu_{low}$ with positive probability. From Paley-Zygmund
inequality we have for $\epsilon>0$ that

$\mathbb{P}(X_{t}\geq(1-\epsilon)\mathbb{E}X_{t})\geq\frac{\epsilon^{2}(\mathbb{E}X_{t})^{2}}{\mathbb{E}X^{2}_{t}}$

and so using $\mathbb{E}X_{t}\geq\mu_{low}\geq\frac{\sqrt{n}}{2},$ we have
$\mathbb{P}(X_{t}\geq(1-\epsilon)\mu_{low})\geq\frac{\epsilon^{2}n}{4\mathbb{E}X^{2}_{t}}.$
From (3.12) and the fact that $k\geq n,$ we then obtain
$\mathbb{E}X^{2}_{t}\leq D_{1}n$ for some constant $D_{1}>0.$ Consequently
$X_{t}\geq(1-\epsilon)\mu_{low}$ with probability at least
$\frac{\epsilon^{2}}{4D_{1}}=:D_{0}.$

Next, using the Chebychev’s inequality, we have for $\epsilon>0$ that

$\mathbb{P}\left(|X_{t}-\mathbb{E}X_{t}|\leq\epsilon\mathbb{E}X_{t}\right)\geq
1-\frac{var(X_{t})}{\epsilon^{2}(\mathbb{E}X_{t})^{2}}.$

Since $\mathbb{E}X_{t}\geq\mu_{low}$ we get from (3.12) that
$\mathbb{P}\left(X_{t}\geq(1-\epsilon)\mu_{low}\right)\geq
1-\frac{D_{2}}{\sqrt{n}}-\frac{D_{3}n}{k}$ for some positive constants
$D_{i}=D_{i}(\epsilon),i=2,3.$ This obtains the second lower bound in (3.2)
and therefore completes the proof of the deviation lower bound in (3.2).

_Proof of ( 3.3)_: We set $t:=\sqrt{bn\log{n}}$ and $s:=\frac{kt}{n}$ so that
the number of segments $I=J$ and use Lemma 4.2 to estimate the probability of
the event $\mathbb{P}(A_{i})=\mathbb{P}(A_{1}).$ By the definition of $t$ and
the fact that $k\geq n,$ we respectively get

$\frac{st}{k}=\frac{t^{2}}{n}=b\log{n}\text{ and
}\frac{s+t}{k}=\frac{t}{k}+\frac{t}{n}\leq\frac{2t}{n}=o(1)$ (3.13)

and so the conditions in Lemma 4.2 are satisfied. Moreover, using $k\geq n$
again, we also get that

$\frac{(s+t)^{2}t}{k^{2}}=\frac{t^{3}(k+n)^{2}}{k^{2}n^{2}}\leq\frac{4t^{3}}{n^{2}}=\frac{4(b\log{n})^{3/2}}{\sqrt{n}}$
(3.14)

Plugging (3.13) and (3.14) into the upper bound of (A.2), we get that

$\displaystyle\mathbb{P}(A_{1}^{c})$ $\displaystyle\leq$ $\displaystyle
e^{-b\log{n}}\cdot\exp\left(\frac{16(b\log{n})^{3/2}}{\sqrt{n}}\right)$
$\displaystyle=$
$\displaystyle\exp\left(-b\log{n}\left(1-16\sqrt{\frac{b\log{n}}{n}}\right)\right)$
$\displaystyle\leq$ $\displaystyle\exp\left(-\frac{b\log{n}}{2}\right)$

for all $n$ large since $b\leq\frac{n}{(32)^{2}\log{n}}$ (see statement of
Theorem 3.1) and so by the union bound we get that $\bigcap_{i=1}^{n/t}A_{i}$
occurs with probability at least

$1-\frac{n}{t}\cdot\exp\left(-\frac{b}{2}\log{n}\right)\geq
1-n\cdot\exp\left(-\frac{b}{2}\log{n}\right).$

This in turn implies that $T_{n}\geq
X_{t}=\frac{n}{t}=\sqrt{\frac{n}{b\log{n}}}$ with probability least
$1-n\cdot\exp\left(-\frac{b}{2}\log{n}\right),$ completing the proof of (3.3).

##  4 Conclusion

In this paper, we have studied coloured and dependent planar matchings in
random bipartite graphs. In the colouring part, we have shown that the largest
rainbow matching is a non-trivial fraction of the total number of colours with
high probability. This hints at a possible transition point with respect to
the colouring parameter. In the dependent setting, we have obtained estimates
on the largest size of a planar matching and also explained our results in
terms of longest increasing subsequences in random enlarged permutations.

## Appendix

Throughout we use the following standard deviation estimate.

######  Lemma 4.1.

Let $\\{X_{j}\\}_{1\leq j\leq r}$ be independent Bernoulli random variables
with

$\mathbb{P}(X_{j}=1)=1-\mathbb{P}(X_{j}=0)>0.$

If $T_{r}:=\sum_{j=1}^{r}X_{j},\theta_{r}:=\mathbb{E}T_{r}$ and
$0<\gamma\leq\frac{1}{2},$ then

$\mathbb{P}\left(\left|T_{r}-\theta_{r}\right|\geq\theta_{r}\gamma\right)\leq
2\exp\left(-\frac{\gamma^{2}}{4}\theta_{r}\right)$ (A.1)

for all $r\geq 1.$

For a proof of (A.1), we refer to Corollary A.1.14, pp. 312 of Alon and
Spencer (2008).

To prove Lemma 3.1, we use the following preliminary result that obtains
estimates on the probability of the events $A_{i}^{c}$ and $A_{i}^{c}\cap
A_{j}^{c}.$

######  Lemma 4.2.

Let $1\leq t\leq n$ and $1\leq s\leq k$ be any two integers satisfying
$\frac{s+t}{k}\leq\frac{1}{8}.$ We have that

$\exp\left(-\frac{st}{k}-\frac{8(s+t)^{2}t}{k^{2}}\right)\leq\mathbb{P}(A_{1}^{c})\leq\exp\left(-\frac{st}{k}+\frac{4(s+t)^{2}t}{k^{2}}\right)$
(A.2)

and

$\mathbb{P}(A_{1}^{c}\cap
A_{2}^{c})\leq\mathbb{P}(A_{1}^{c})\mathbb{P}(A_{2}^{c})\exp\left(\frac{5t^{2}}{k}\right).$
(A.3)

_Proof of ( A.2) in Lemma 4.2_: For any integer $1\leq l\leq n$ and $l$
distinct integers $1\leq a_{1},\ldots,a_{l}\leq n,$ we have that

$\mathbb{P}(u_{1}=a_{1},\ldots,u_{l}=a_{l})=\frac{1}{k(k-1)\ldots(k-l+1)}.$
(A.4)

Let $\pi(i)$ be the $x-$coordinate of the top vertex adjacent to $u_{i}$ in
the graph $G.$ If the event $A_{1}^{c}$ occurs, then the number of choices for
$\pi(1)$ is $k-s.$ Similarly, given $\pi(1),$ the number of choices for
$\pi(2)$ is $k-s-1$ and so on. Thus the number of choices for the $t-$tuple
$(\pi(1),\ldots,\pi(t))$ is

$(k-s)\cdot(k-s-1)\cdots(k-s-t+1)$

and so we get from (A.4) that

$\displaystyle\mathbb{P}(A_{1}^{c})$ $\displaystyle=$
$\displaystyle\frac{(k-s)\cdot(k-s+1)\ldots(k-s-t+1)}{k(k-1)\cdots(k-t+1)}$
(A.5) $\displaystyle=$
$\displaystyle\frac{\left(1-\frac{s}{k}\right)\cdots\left(1-\frac{s+t-1}{k}\right)}{\left(1-\frac{1}{k}\right)\cdots\left(1-\frac{t-1}{k}\right)}.$

Using $\frac{s+t}{k}\leq\frac{1}{4}$ we get for all $x\leq\frac{2(s+t)}{k}$
that

$\displaystyle\frac{e^{-x}}{1-x}$ $\displaystyle=$ $\displaystyle
1+\frac{1}{1-x}\left(\frac{x^{2}}{2!}-\frac{x^{3}}{3!}+\ldots\right)$ (A.6)
$\displaystyle\leq$ $\displaystyle 1+\frac{2x^{2}}{1-x}$ $\displaystyle\leq$
$\displaystyle 1+4x^{2}.$

Thus

$e^{-x}\cdot\left(1+\frac{4(s+t)^{2}}{k^{2}}\right)^{-1}\leq 1-x\leq e^{-x}.$
(A.7)

Plugging the upper bound of (A.7) into the numerator of (A.5) and the lower
bound of (A.7) into the denominator, we get that $\mathbb{P}(A_{1}^{c})\leq
I_{1}\cdot I_{2}$ where

$I_{1}:=\frac{\exp\left(-\frac{1}{k}\sum_{l=s}^{s+t-1}k\right)}{\exp\left(-\frac{1}{k}\sum_{l=1}^{t-1}k\right)}=\exp\left(-\frac{st}{k}\right)$
(A.8)

and

$I_{2}:=\left(1+\frac{4(s+t)^{2}}{k^{2}}\right)^{t}\leq\exp\left(\frac{4(s+t)^{2}t}{k^{2}}\right).$

This obtains the upper bound in (A.2).

Similarly, substituting the lower bound of (A.7) into the numerator of (A.5)
and the upper bound of (A.7) into the denominator, we get that

$\mathbb{P}(A_{1}^{c})\geq
e^{-\frac{st}{k}}\cdot\left(1+\frac{4(s+t)^{2}}{k^{2}}\right)^{-t}\geq
e^{-\frac{st}{k}}\cdot\left(1-\frac{4(s+t)^{2}}{k^{2}}\right)^{t}.$ (A.9)

Again using $\frac{s+t}{k}\leq\frac{1}{2}$ and the fact that $1-x\geq e^{-2x}$
for all $x<\frac{1}{2},$ we get the lower bound in (A.2) from the final
expression in (A.9).

_Proof of ( A.3) in Lemma 4.2_: We use a split set argument and as before,
$\pi(i),1\leq i\leq n$ is the $x-$coordinate of the top vertex adjacent to
$u_{i},$ in the graph $K_{k,n}.$ For a deterministic set ${\cal
Q}_{1}\subseteq\\{1,2,\ldots,t\\},$ let $F_{1}({\cal Q}_{1})$ be the event
that $\pi(j)\in\\{s+1,\ldots,2s\\}$ for every integer $j\in{\cal Q}_{1}$ and
$\pi(l)\notin\\{1,2,\ldots,2s\\}$ for every
$l\in\\{1,2,\ldots,t\\}\setminus{\cal Q}_{1}.$ Similarly for ${\cal
Q}_{2}\subseteq\\{t+1,\ldots,2t\\},$ let $F_{2}({\cal Q}_{2})$ be the event
that $\pi(j)\in\\{1,\ldots,s\\}$ for every integer $j\in{\cal Q}_{2}$ and
$\pi(j)\notin\\{1,2,\ldots,2s\\}$ for every
$j\in\\{t+1,\ldots,2t\\}\setminus{\cal Q}_{2}.$ By definition we then have
that

$A_{1}^{c}\cap A_{2}^{c}=\bigcup_{{\cal Q}_{1},{\cal Q}_{2}}F_{1}({\cal
Q}_{1})\cap F_{2}({\cal Q}_{2}),$ (A.10)

where the union is over all sets ${\cal Q}_{1}\subseteq\\{1,2,\ldots,t\\}$ and
${\cal Q}_{2}\subseteq\\{t+1,\ldots,2t\\}.$ Thus

$\mathbb{P}(A_{1}^{c}\cap A_{2}^{c})=\sum_{j_{1},j_{2}}\;\;\;\sum_{\\#{\cal
Q}_{1}=j_{1}}\sum_{\\#{\cal Q}_{2}=j_{2}}\mathbb{P}\left(F_{1}({\cal
Q}_{1})\cap F_{2}({\cal Q}_{2})\right).$ (A.11)

Letting $(a)_{b}:=\left\\{\begin{array}[]{cc}a(a-1)\cdots(a-b+1)&\text{ if
}b\geq 1\\\ 1&\text{ if }b=0,\end{array}\right.$ we have that

$\mathbb{P}(F_{1}({\cal Q}_{1}))=\frac{(s)_{j_{1}}(k-2s)_{t-j_{1}}}{(k)_{t}}.$

A similar expression holds for $F_{2}({\cal Q}_{2})$ and the intersection
$F_{1}({\cal Q}_{1})\cap F_{2}({\cal Q}_{2}).$ Letting
$j_{low}:=\min(j_{1},j_{2})$ and $j_{up}:=\max(j_{1},j_{2})$ and combining the
above expressions, we get that

$\frac{\mathbb{P}(F_{1}({\cal Q}_{1})\cap F_{2}({\cal
Q}_{2}))}{\mathbb{P}(F_{1}({\cal Q}_{1}))\mathbb{P}(F_{2}({\cal
Q}_{2}))}=\frac{f(k-2s,t-j_{low},t-j_{up})}{f(k,t,t)},$ (A.12)

where $f(a,b,c):=\frac{(a-b)_{c}}{(a)_{c}}.$

Suppose $c\geq 1$ and $\frac{b+c}{a}<\frac{1}{2}.$ We rewrite

$f(a,b,c)=\prod_{j=0}^{c-1}\left(1-\frac{b+j}{a}\right)\cdot\prod_{j=1}^{c-1}\left(1-\frac{j}{a}\right)^{-1}$

and use the estimate $e^{-2x}\leq 1-x\leq e^{-x}$ for $x<\frac{1}{2}$ to get
that

$f(a,b,c)\leq\prod_{j=0}^{c-1}\exp\left(-\frac{b+j}{a}+\frac{2j}{a}\right)\leq
e^{-\frac{bc}{a}+\frac{c^{2}}{a}}\leq e^{\frac{c^{2}}{a}}.$ (A.13)

Similarly

$f(a,b,c)\geq\prod_{j=1}^{c}\exp\left(-\frac{2b+2j}{a}+\frac{j}{a}\right)=e^{-\frac{2bc}{a}}\exp\left(-\sum_{j=1}^{c}\frac{j}{a}\right)\geq
e^{-\frac{2bc}{a}-\frac{c^{2}}{a}}.$ (A.14)

We now use (A.13) with $a=k-2s,b=t-j_{low}$ and $c=t-j_{up}$ to evaluate
$f(k-2s,t-j_{low},t-j_{up}).$ We have that

$\frac{b+c}{a}=\frac{2t-j_{1}-j_{2}}{k-2s}\leq\frac{2t}{k-2s}\leq\frac{4t}{k}<\frac{1}{2}$
(A.15)

where the second inequality in (A.15) follows from
$\frac{s}{k}<\frac{s+t}{k}\leq\frac{1}{4}$ and the third inequality in (A.15)
again follows from $\frac{t}{k}<\frac{s+t}{k}\leq\frac{1}{8}$ (see statement
of Lemma 4.2). From (A.13) we therefore have

$f(k-2s,t-j_{low},t-j_{up})\leq\exp\left(\frac{(t-j_{up})^{2}}{k-2s}\right)\leq\exp\left(\frac{t^{2}}{k-2s}\right)\leq\exp\left(\frac{2t^{2}}{k}\right)$
(A.16)

since $\frac{s}{k}\leq\frac{s+t}{k}\leq\frac{1}{4}.$ Similarly, using (A.14)
with $a=k,b=c=t$ we get that

$f(k,t,t)\geq\exp\left(-\frac{3t^{2}}{k}\right)$ (A.17)

Plugging (A.16) and (A.17) into (A.12), we get that

$\frac{\mathbb{P}(F_{1}({\cal Q}_{1})\cap F_{2}({\cal
Q}_{2}))}{\mathbb{P}(F_{1}({\cal Q}_{1}))\mathbb{P}(F_{2}({\cal
Q}_{2}))}\leq\exp\left(\frac{5t^{2}}{k}\right).$ (A.18)

Substituting (A.18) into (A.11) and summing over ${\cal Q}_{1}$ and ${\cal
Q}_{2},$ we get (A.3).

### Acknowledgement

I thank Professors Rahul Roy, C. R. Subramanian and the referee for crucial
comments that led to an improvement of the paper. I also thank IMSc and IISER
Bhopal for my fellowships.

## References

  * [1] J. Baik, P. Deift and K. Johansson. (1999).  On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations.  Journal of the American Mathematical Society, 12, pp. 1119–1178.
  * [2] B. Bollobás. (2001).  Random Graphs.  Cambridge University Press.
  * [3] G. Ganesan. (2021).  Strong and Weighted Matchings in Inhomogenous Random Graphs.  Electronic Communications in Probability, pp. 1–12.
  * [4] J. M. Hammersley. (1972).  A Few Seedlings of Research.  Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, pp. 345–294.
  * [5] B. F. Logan and L. A. Shepp. (1977).  A Variational Problem for Random Young Tableaux.  Advances in Mathematics, 26, pp. 206–222.
  * [6] M. Kiwi and M. Loebl. (2002).  Largest Planar Matching in Random Bipartite Graphs.  Random Structures and Algorithms, 21, 162–181.
  * [7] M. Kiwi and M. Loebl. (2008).  Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraphs in Random Bipartite Graphs.  Electronic Journal of Combinatorics, 15:R135, 1–20.
  * [8] K. Johansson. (2000).  Shape fluctuations and random matrices.  Communications in Mathematical Physics, 209, 437–476.
  * [9] D. Romik. (2014).  The Surprising Mathematics of Longest Increasing Subsequences.  Cambridge University Press.
  * [10] S. Ulam. (1961).  Monte Carlo Calculations in Problems of Mathematical Physics.  Modern Mathematics For the Engineer (McGraw-Hill), pp. 261–281.
  * [11] A. M. Vershik and S. V. Kerov. (1977).  Asymptotics of the Plancherel Measure of the Symmetric Group and the Limiting Shape of Young Tableaux.  Soviet Mathematics Doklady, 18, pp. 527–531.