# Generative Adversarial Network with Multi-Branch Discriminator
for Cross-Species Image-to-Image Translation

Ziqiang Zheng  Zhibin Yu  Haiyong Zheng  Yang Wu  Bing Zheng  Ping Lin

###### Abstract

Current approaches have made great progress on image-to-image translation
tasks benefiting from the success of image synthesis methods especially
generative adversarial networks (GANs). However, existing methods are limited
to handling translation tasks between two species while keeping the content
matching on the semantic level. A more challenging task would be the
translation among more than two species. To explore this new area, we propose
a simple yet effective structure of a multi-branch discriminator for enhancing
an arbitrary generative adversarial architecture (GAN), named GAN-MBD. It
takes advantage of the boosting strategy to break a common discriminator into
several smaller ones with fewer parameters, which can enhance the generation
and synthesis abilities of GANs efficiently and effectively. Comprehensive
experiments show that the proposed multi-branch discriminator can dramatically
improve the performance of popular GANs on cross-species image-to-image
translation tasks while reducing the number of parameters for computation. The
code and some datasets are attached as supplementary materials for reference.

##  1 Introduction

Figure 1: Semantic level matching through cross-species image-to-image
translation tasks by our proposed method.

The generative adversarial network (GAN), which has been developed by
Goodfellow (Goodfellow et al., 2014), is a proven and powerful framework used
to handle various computer vision tasks, such as generating pictures from text
descriptions (Reed et al., 2016; Zhang et al., 2017c), converting video from
still images (Chan et al., 2018), increasing the resolution of images (Ledig
et al., 2017), and editing and translating images/videos (Zhang et al., 2018,
2017a; Isola et al., 2017; Zhu et al., 2017; Wang et al., 2018c; Zhang et al.,
2017b; Wang et al., 2018a; Lee et al., 2018; Huang et al., 2018b; Wang et al.,
2018b). In particular, as an important and applicable topic in computer
vision, GAN-based image-to-image translation has attracted more and more
attentions (Huang et al., 2018a). Many extensions of the GAN have focused on
how to enhance the generation and synthesis ability to obtain better image
translation performance by including new loss functions (Arjovsky et al.,
2017; Xudong Mao & Wang, 2016), complex architectures (Zheng et al., 2018) and
multiple networks (Durugkar et al., 2017; Zhu et al., 2017; Kim et al., 2017;
Yi et al., 2017).

While research is still underway to improve training techniques and heuristics
in one domain (Lahiri et al., 2018), some approaches have focused on designing
powerful cross-domain translation architectures (Choi et al., 2018). Unlike
the domain crossing approach which aims to translate images from one domain to
another, we propose the cross-species image-to-image translation tasks that
are about obtaining semantic level matching among two or more species during
the translation, for which some interesting results are shown in Figure 1.

For a cross-species translation task, a good solution is expected to take into
account of two important aspects. On one hand, it needs to have a high-
performance network on generation, which should be able to handle the inter-
species similarities and intra-species differences at the same time. On the
other hand, the computational load has to be reasonable to make it feasible
for as many application scenarios as possible, for example, using only one
single graphic processing unit (GPU) with a small memory.

However, most existing GANs inefficiently handle cross-species tasks. Some
GANs with high performance are still expensive to train. For example, PGGAN
(Karras et al., 2018) requires 2 weeks of training with a single GPU.
Pix2pixHD (Wang et al., 2018c), which is an extension of the common image-to-
image framework Pix2pix (Isola et al., 2017), requires a GPU with a minimum
memory of 12 GB. Thus, designing a powerful image-to-image architecture with
limited resources is still a serious challenge.

Boosting approach, which is originated from Kearns et al. (1994), described an
idea to construct a strong learner based on several weak learners. Inspired by
this idea, we can break a discriminator, which is an important component of
GANs, into several branches as weak learners to construct a more powerful and
efficient image-to-image translation model.

To handle the cross-species image-to-image translation task with limited
resources, we propose to use a multi-branch discriminator (MBD) to enhance the
ability of a GAN, with a brief name of GAN-MBD. The contributions and
novelties of this paper are described below:

  * •

We propose a novel structure for GAN to enhance the image-to-image translation
ability while reducing the amount of the parameters needed.

  * •

We provide a recycling and refining method for post-processing to improve the
image generation performance without additional parameters.

  * •

Our architecture can improve most popular image-to-image translation GANs, and
can translate images not only between two species, but also among multiple
species.

##  2 Related work

###  2.1 Image-to-image translation

In general, image-to-image translation describes a task to convert an image of
one domain to an image of another domain. Many typical computer vision topics
can be summarized as image-to-image translation tasks, including semantic
segmentation (Long et al., 2015; Yeh et al., 2017), image restoration and
enhancing (Zhang et al., 2017a; Luo et al., 2015), image editing and in-
painting (Gatys et al., 2015; Pathak et al., 2016; Yang et al., 2017), super
resolution (Ledig et al., 2017; Chen & Tong, 2017; Sønderby et al., 2016). In
some early years, these tasks have been handled with various types of
artificial neural network models (Kingma & Welling, 2013; Rezende et al.,
2014). Due to the success of extensions on a conditional GAN, Isola et al.
(2017) developed an important branch of GAN called Pix2pix to apply
adversarial learning to image-to-image translation. Although Pix2pix can
handle many image-to-image tasks, it used a supervised training method that
always requires paired datasets. To overcome this shortage, Zhu et al. (2017)
proposed another variation called CycleGAN to extend GAN-based image-to-image
translation to unpaired datasets with two generators and two discriminators.
Soon after Choi et al. (2018) further improved this idea and proposed StarGAN
to translate images over multiple datasets with a single generator and
discriminator.

Along with the development of image-to-image translation techniques, many
researchers have chosen unpaired training datasets for image-to-image tasks
(Long et al., 2015). Even so, cross-domain (e.g., cross-species) translation
tasks, are still acknowledged as difficult (Taigman et al., 2016; Lu, 2018). A
recent study called multimodal unsupervised image-to-Image translation (MUNIT)
used an unsupervised multimodal structure to translate styles as well as
contents to rebuild the target images (Huang et al., 2018b). Lee et al. (2018)
proposed a disentangled representation framework to generate diverse outputs
with unpaired training data. Gokaslan et al. (2018) presented another
unsupervised image-to-image translation framework based on a discriminator
with dilated convolutions. Li (2018) used a progressively growing skip
connected encoder-generator structure for human-anime character translation.
However, none of these methods considers optimizing the performance and
reducing the number of parameters of the discriminator. On the contrary, in
order to gain the performance of GANs for image generation and synthesis, most
work adopted more than one generator or discriminator, increasing the
parameters as well as the computational cost dramatically. Moreover, the study
on more challenging cross-species image-to-image translation is rare.

###  2.2 Boosting for GANs

Boosting is an important branch of machine learning algorithms that construct
a strong learner based on several weak learners (Zhou, 2012; Kearns & Valiant,
1994). Generally, a weak learner is defined as a classifier that has only a
slight advantage over random guessing on the given classification task. In
contrast, a well-performed classifier can be defined as a strong learner. The
original boosting algorithms were not adaptive and could not take full
advantage of the weak learners (Schapire, 1990; Mason et al., 2000). Schapire
and Freund (2012) then developed AdaBoost, a typical adaptive boosting
algorithm which can be applied to many cases (Kégl, 2013).

The key idea of a boosting algorithm is to construct a powerful classifier
based on multiple weak classifiers. Following the idea, Durugkar et al. (2017)
considered the discriminator to be a weak classifier and proposed generative
multi-adversarial networks to apply the boosting concept to GAN. Many
approaches have attempted to include multiple discriminators to enhance
generation performance. Multi-discriminator CycleGAN (Hosseini-Asl et al.,
2018), which is an extension of CycleGAN, was proposed to enhance the speech
domain adaption with a multiple discriminators architecture. Hardy et al.
(2018) proposed MD-GAN to use a GAN with multiple discriminators on the
distributed datasets. Most of studies have used multiple powerful
discriminators to give the generator with better guidance. However, the more
discriminators we have, the more parameters we need, while more parameters
lead to higher memory cost and longer training time. Different from previous
work with multiple discriminators for boosting, we break a discriminator into
multiple branches in channels, which takes advantage of multiple
discriminators while reducing the number of parameters and the computational
cost.

Figure 2: The overview of the proposed GAN-MBD model.

##  3 Methods

###  3.1 Network architecture

Many GAN based image-to-image models use encoder-decoder structures (Isola et
al., 2017; Choi et al., 2018; Zhu et al., 2017). Following this idea, we
propose a general structure for GANs on image-to-image translation tasks as
shown in Figure 2. Inspired by AdanIN (Huang & Belongie, 2017), we use two
conditional maps to include the bias information of the original images and
the bottlenecks. The conditional map $C_{O}$ emphasizes the label for the
original image, and the map $C_{T}$ denotes the target label that we want to
translate. There is a full connection between the one-hot encoded label and
the conditional map. Please note that $W_{O}$ and $W_{T}$ are two individual
weights. Considering that there may exist multiple layers on the bottleneck
position (Choi et al., 2018; Zhu et al., 2017), we place the target
conditional map $C_{T}$ on the last layer of the bottleneck. Then we design a
discriminator with multiple branches to distinguish between true and false
images. For multiple class translation cases, we also use these branches to
detect the image class. We define the translation process as converting an
image of a species to another type. Enlightened by Bansal et al.’s work
(2018), we provide an optional recycling process to enhance the image quality.
The recycling process still uses the same network without additional
parameters that is used for the translation process. Because the recycling
process does not change the image identity, the conditional map $C_{T}$ can be
used at both input and bottleneck positions ($C_{T}=C_{O}$).

###  3.2 Multi-branch discriminator (MBD)

Figure 3: The difference between a common discriminator and a 4-branch
discriminator.

Suppose a common discriminator has $X$ channels for the $n_{th}$ layer.
Instead, our discriminator with $m$ branches has $X/m$ channels for each
branch of the $n_{th}$ layer. Each branch that can be considered as a weak
discriminator works independently. Notably, the number of parameters of a
discriminator with two branches would only be half of a common discriminator.
Theoretically, we could obtain fewer parameters if we used more branches. As
shown in Figure 3, a traditional discriminator of GAN can be considered as a
special case of a discriminator with multiple branches (only one branch case).
For the general case, each branch should be able to handle two tasks. The
first task is to decide whether the current image is real or synthesized.
Another parallel task of each branch is to judge the image category whether or
not the image is real or fake. The average output of all branches will be the
final result of the discriminator. The loss function of our model is:

$\begin{split}\mathcal{L}(G,D)=\frac{1}{N}\sum_{i}^{N}{\\{\mathbb{E}_{y\sim
P_{data}(y)}\left[\log D_{i}(y)\right]}+\\\ \mathbb{E}_{x\sim
P_{data}(x)}\left[\log(1-D_{i}(G(x|c_{in},c_{bn}))\right]\\}+\mathcal{L}_{cls}\end{split}$
(1)

where $x$ denotes the original real images, $y$ means the target real images,
$D_{i}$ is the $i_{th}$ branch of discriminator $D$, $N$ is the total number
of branches, and $c_{in}$ and $c_{bn}$ denote the conditional map used in the
input and bottleneck positions respectively. In the recycling process,
$c_{in}=C_{O}$ and $c_{bn}=C_{T}$. In the recycling process,
$c_{in}=c_{bn}=C_{T}$. $\mathcal{L}_{cls}$ is the category classification loss
which can be written below:

$\begin{split}\mathcal{L}_{cls}=\frac{1}{N}\sum_{i}^{N}{\\{\mathbb{E}_{y,c}[{-logD_{cls,i}(c|y)}]}+\\\
\mathbb{E}_{x,c}[{-logD_{cls,i}(c|G(x,c_{in},c_{bn}))}]\\}\end{split}$ (2)

where the first and the second terms denote the classification loss for real
images and fake images respectively; and $D_{cls,i}$ means the category
identification task for the $i_{th}$ branch.

###  3.3 Recycling and refining

Figure 4: Details of the translation process and the recycling process.

To generate more plausible results, we develop an optional recycling
architecture to improve the generated outputs. As shown in Figure 4, the
output image of the generator after translation process in the first stage is
reused as the input of the generator in the second stage for refinement.
Notably, the recycling process still uses the same parameters that used in the
translation process. Unlike the translation process, the image category will
not be changed in the recycling process. Thus, the conditional map on the
bottleneck is the same as that on the input position. Considering that the
recycling process might be unstable in the early training stage, we freeze the
recycling operation until the current epoch number is larger than half of the
total number of epochs.

Additionally, we provide another optional individual refining process as a
post-processing approach to remove noise and further enhance the quality of
the final outputs. The details of this process are described in Figure 5. We
compress the training samples used for the recycling process from $256\times
256$ to $32\times 32$ and then enlarge them back to $256\times 256$ as the
training inputs of the refinement using the nearest-neighbor interpolating
rule. The original $256\times 256$ images are used as training targets. We
choose Pix2pix, which is a general image-to-image architecture, to implement
this task.

Figure 5: Details of the refining process.

##  4 Experiments

In this section, we describe the detailed experiments to evaluate our proposed
approach.

###  4.1 Datasets

Cat2dog is a cropped image dataset including 1000 cat images and 1200 dog
images in total. We inherit this dataset from Disentangled Representation for
Image-to-Image Translation (DRIT) (Lee et al., 2018), and we follow the same
data split for training and testing.

CelebA is a large scale face dataset (Liu et al., 2015) in the wild, which
contains approximately 200 thousand images. In our task, to maintain the
balance of each category, we randomly selected 1000 images from this dataset
to achieve image-to-image translation between different species.

102Flowers is a flower dataset (Nilsback & Zisserman, 2008) in the wild, which
contains 102 different categories of flowers. In our experiments, we randomly
choose five categories of flower images (grape hyacinth, water lily, rose,
thorn apple and hibiscus) including 704 images for training and 174 images for
testing.

Labeled faces in the wild (LFW) is another facial dataset (Learned-Miller et
al., 2016) that contains more than 13,000 images. Compared with CelebA, LFW
includes more poses and complex situations, such as two people included in one
image. We randomly choose 1002 images from this dataset for the flower-to-
human image translation task in the wild, among which 804 images are used for
training and 198 images are used for testing.

Dogs vs. Cats $|$ Kaggle is another dog and cat image dataset (Elson et al.,
2007) that includes 25,000 images. This dataset is more challenging than the
Cat2dog dataset because the cat and dog images are captured in the wild. We
randomly select 1000 cat images from this dataset to explore the potential of
our method on image-to-image tasks in the wild.

###  4.2 Evaluation metric

The inception score (Salimans et al., 2016) can be considered a good
assessment of sample quality from a labeled dataset. This score is consistent
with the idea that a good synthetic sample should achieve a high confidence
score when using a strong classifier, and it is defined as follows:

$\exp(\mathbb{E}_{x}KL(p(y|x)||p(y)))$ (3)

where $x$ denotes one sample, and $p(y|x)$ is the softmax output of a trained
classifier of the labeled datasets, and $KL$ indicates the Kullback-Leibler
divergence. We apply InceptionV3 model on the images generated by different
methods to achieve label distribution $p(y|x)$. Images that contain meaningful
objects have a conditional label distribution with low entropy; the inception
score metric is good for evaluation and correlates well with human judgment.

###  4.3 Comparison with state-of-the-art methods

General image-to-image translation tasks with MBD

We first evaluate the effectiveness of multiple branches. Figure 6 shows an
example of a dog-cat translation task. In this experiment, we apply our
architecture based on CycleGAN (Zhu et al., 2017). The discriminators of
CycleGAN have a minimum of 64 channels. Thus, we can set a maximum branch
number of 64 in our model. However, the more branches we have, the fewer
parameters and channels we use in one branch. Actually, we can obtain good
translation results when we use 2-4 branches. Notably, the poses of the cats
(dogs) are well translated by our model. The results become worse when the
number of branches is larger than 8, which indicates that one branch should
not have too few channels. We also check the inception score of the generated
images on cat-to-dog, dog-to-cat, human-to-flower and flower-to-human tasks in
Table 1 and Table 2. We find that the inception score obtained by 2 or 4
branches is relatively high, and in most cases having 4 branches is always
better than 2 branches. Therefore, we choose the CycleGAN with 4 branches for
the following image-to-image translation tasks between two species.

Figure 6: The cat-dog translation results using CycleGAN with different number of branches ($n$BR means $n$ branches). Table 1: Inception score results on cat-dog translation tasks using CycleGAN with different number of branches. Method | cat to dog | dog to cat
---|---|---
CycleGAN |  1.4839 $\pm$ 0.1045 |  1.4359 $\pm$ 0.0565
CycleGAN-2br |  1.4799 $\pm$ 0.1094 |  1.4277 $\pm$ 0.1636
CycleGAN-4br | 1.6007 $\pm$ 0.2081 | 1.4524 $\pm$ 0.1716
CycleGAN-8br |  1.4351 $\pm$ 0.1720 |  1.4154 $\pm$ 0.0928
CycleGAN-16br |  1.3629 $\pm$ 0.1150 |  1.4157 $\pm$ 0.1680
CycleGAN-32br |  1.3175 $\pm$ 0.1003 |  1.2731 $\pm$ 0.0775
$n$br means $n$ branches |  |
Table 2: Inception score results on flower-human translation tasks using CycleGAN with different number of branches. Method | human to flower | flower to human
---|---|---
CycleGAN |  1.1256 $\pm$ 0.0732 |  1.1045 $\pm$ 0.0615
CycleGAN-2br |  1.2991 $\pm$ 0.1540 | 1.2618 $\pm$ 0.1040
CycleGAN-4br | 1.4002 $\pm$ 0.0915 |  1.2517 $\pm$ 0.0477
CycleGAN-8br |  1.1628 $\pm$ 0.0327 |  1.0658 $\pm$ 0.0223
CycleGAN-16br |  1.0959 $\pm$ 0.0420 |  1.0528 $\pm$ 0.0586
CycleGAN-32br |  1.0873 $\pm$ 0.0423 |  1.0684 $\pm$ 0.0285
$n$br means $n$ branches |  |

Image-to-image translation task between two species

Cat$\Leftrightarrow$Dog. As mentioned by Zhu et al. (2017), unpaired image-to-
image translation between a cat and a dog is an open puzzle. We still use
CycleGAN with our architecture and the Cat2dog dataset for this task. We
compare our method with two state-of-the-art methods: MUNIT (Huang et al.,
2018b) and DRIT (Lee et al., 2018) in Figure 7. The sub-images shown in Figure
7 are listed according to “input-output” order. We find that the images
generated by CycleGAN with 4 branches exhibits the best performance. Notably,
the generated dogs (cats) of our method still maintain the same poses as those
of the input images. Table 3 shows the inception scores of three models.
CycleGAN with 4 branches has the highest scores on both cat-to-dog and dog-to-
cat tasks.

Figure 7: The cat-dog translation results of our CycleGAN-4BR compared with MUNIT and DRIT. Table 3: Inception score results of different methods on cat-dog translation tasks. Method | cat to dog | dog to cat
---|---|---
DRIT |  1.4774 $\pm$ 0.1072 |  1.4337 $\pm$ 0.1197
MUNIT |  1.4935 $\pm$ 0.1436 |  1.4256 $\pm$ 0.1252
CycleGAN-4br | 1.6007 $\pm$ 0.2081 | 1.4524 $\pm$ 0.1716

Cat$\Leftrightarrow$Flower. The second experiment was implemented between
102Flowers and Cat2dog datasets. Here we only choose cats for this two species
translation task. The experiment results are shown in Figure 8. Compared with
the image-to-image translation between cats and dogs, flowers do not have pose
or facial information. Thus, it is not possible to expect a semantic pose
matching between flowers and cats. However, Figure 8 shows that our method is
able to obtain a number and position matching between these two species. We
also compare our method with two state-of-the-art methods in this experiment
in Figure 9. Both MUNIT and DRIT can successfully translate images, while the
input image only includes a single individual. However, these two methods fail
to convert two flowers to two cats while our method can still do so.

Figure 8: The cat-flower translation results of our CycleGAN-4BR. Figure 9:
The cat-flower translation results of our CycleGAN-4BR compared with MUNIT and
DRIT.

To explore the potential of our method, we implement a more challenging
experiment based on the Dogs vs. Cats $|$ Kaggle and 102Flowers datasets. The
results are displayed in Figure 10. In this experiment, both flowers and cats
are captured in the wild. We find that our model can still translate a cat
image to another flower image successfully. Our method can generate the head
of a cat from a flower image but cannot generate the full body of a cat.

Figure 10: The wild cat-flower translation results of our CycleGAN-4BR.

Cat$\Leftrightarrow$Human. We designed another experiment for two species
image-to-image translation between the CelebA and Cat2dog datasets. Similar to
the previous experiments, we compare our method with MUNIT and DRIT in Figure
11. More results can be found in the supplementary file. Please note that the
generated images by our method follow the semantic pose matching on both cat-
to-human and human-to-cat experiments.

Figure 11: The cat-human translation results of our CycleGAN-4BR compared with
MUNIT and DRIT.

Flower$\Leftrightarrow$Human. We also evaluate the image-to-image translation
performance between the 102Flowers and CelebA datasets. Comparison results are
shown in Figure 12 and more translation results are displayed in the
supplementary file. All 3 methods can basically accomplish a human-to-flower
translation task. However, the flower-to-human translation task seems more
challenging. Images generated by MUNIT or DRIT always have a serious
distortion while our method can still achieve a reasonable solution. Table 4
also illustrates that our method can obtain the best results against MUNIT and
DRIT in terms of inception score.

Figure 12: The flower-human translation results of our CycleGAN-4BR compared with MUNIT and DRIT. Table 4: Inception score results of different methods on flower-human translation task. Method | human to flower | flower to man
---|---|---
DRIT |  1.1572 $\pm$ 0.0481 |  1.2010 $\pm$ 0.0778
MUNIT |  1.3451 $\pm$ 0.1352 |  1.1706 $\pm$ 0.1148
CycleGAN-4br | 1.4002 $\pm$ 0.0915 | 1.2517 $\pm$ 0.0477

Similar to the experiment described in Figure 10, we design another
challenging experiment based on the LFW and 102Flowers datasets. Both datasets
are captured in the wild. As shown in Figure 13, our method can handle most of
the human-to-flower cases. Although we find some unreasonable distortion, we
can still observe the position and number matching in the wild flower-to-human
task.

Figure 13: The wild flower-human translation results of our CycleGAN-4BR.

Image-to-image translation task among multiple species

Considering that both CycleGAN (Zhu et al., 2017) and Pix2pix (Isola et al.,
2017) can only handle image-to-image tasks between 2 classes, we choose
StarGAN (Choi et al., 2018) under our architecture with 4 branches for the
multiple species translation task. The multiple species translation task is
more difficult than that between two species. We use the optional recycling
and refining process mentioned in Section 3.3 to enhance the outputs. We chose
3 species, including human from CelebA, cat and dog from Cat2dog to implement
this task. The experimental results are shown in Figure 14 and Figure 15. We
find that StarGAN cannot handle the cross-species task without the help of
multiple branches. The recycling and refinement of the post-processing
approach, introduced in Section 3.3, can actually improve the output image
quality for translation tasks among multiple species.

Figure 14: The multiple species translation results of our StarGAN-4BR without recycling, with recycling, with recycling and refining (proposed). Figure 15: The cat-dog-human translation results of our StarGAN-4BR (proposed) compared with StarGAN. Table 5: Parameter statistics based on different methods using multi-branch discriminator. The values in the brackets represent the parameter number of the discriminator while the values outside the brackets shows the total parameter number (millions) of the GANs. Branches | 1 | 2 | 4 | 8 | 16 | 32 | 64
---|---|---|---|---|---|---|---
Pix2pix | 57.18(2.77) | 55.80(1.39) | 55.11(0.70) | 54.77(0.36) | 54.60(0.19) | 54.51(0.10) | 54.47(0.06)
CycleGAN | 36.69(13.92) | 29.74(6.98) | 26.27(3.50) | 24.53(1.77) | 23.66(0.90) | 23.22(0.46) | 23.01(0.24)
StarGAN | 58.31(45.41) | 35.96(23.06) | 24.79(11.89) | 19.20(6.30) | 16.41(3.51) | 15.01(2.11) | 14.31(1.41)

##  5 Discussion

Table 6: Parameter evaluation (1K=1000 iterations). Method | Parameter | Time (1K) | Multi-Species
---|---|---|---
DRIT | 104.24 | 2570.49 | False
MUNIT | 44.76 | 418.58 | False
CycleGAN-2br | 29.74 | 461.30 | False
CycleGAN-4br | 26.27 | 595.91 | False
StarGAN | 58.31 | 373.44 | True
StarGAN-2br | 35.96 | 342.13 | True
StarGAN-4br | 24.79 | 315.42 | True
StarGAN-4br-recycle | 24.79 | 370.33 | True
Figure 16: The results of our CycleGAN-MBD (proposed) and CycleGAN with
multiple discriminators on different datasets.

Essentially, a GAN with a multi-branch discriminator can be considered a
special variant of a GAN with multiple discriminators. Many studies have shown
that multiple discriminators can enhance the performance of various GANs
(Hosseini-Asl et al., 2018; Hardy et al., 2018). However, none of these
studies have investigated the potential of reducing the discriminator
parameters while improving the generation ability. Actually, it is not
sensible to expand too many discriminators for a GAN due to the parameter
explosion problem. A parameter evaluation is given in Table 5. Suppose two
adjacent layers in the original discriminator have $r$ channels and $t$
feature maps, there would be $r\times t$ connection between these two layers.
We would have $2rt$ connections if we use 2 discriminators. When we divide a
discriminator into two branches, the channel number of the discriminator would
also be divided. Thus, each branch only has $\frac{r}{2}$ channels and
$\frac{t}{2}$ feature maps, and 2 branches would have $\frac{r\times t}{2}$
connections. We design an experiment to evaluate the effectiveness of the
CycleGAN with multiple discriminators and MBD. We compare 2BR and 4BR with 2
and 4 discriminators respectively as shown in Figure 16. We find that a
CycleGAN with MBD has similar generation performance to a CycleGAN with
multiple discriminators when the branch number is larger than 4. However, a
branch has much fewer parameters than a complete discriminator. We also
compare our model with state-of-the-art methods in Table 6 to evaluate the
parameter number and the running speed (every 1000 iterations). All models are
implemented in the same environment (Intel Xeon E5-2620 v4, 128 GB, 1080 Ti,
TensorFlow 1.8.0). Obviously, the model with multi-branch structure has fewer
parameters and faster training speeds. More evaluation results can be found in
the supplementary file.

##  6 Conclusion

In this paper, we develop a novel, simple yet effective multi-branch
discriminator (MBD) structure for GANs, leading to high-quality cross-species
image-to-image translation. The proposed MBD structure can improve most
popular GANs, for efficiently enhancing the generative and synthesis ability
while reducing the model parameters dramatically. Furthermore, We provide a
recycling and refining post-processing method to improve the results for
multiple cross-species image-to-image translation tasks. We also show the
potential of our method to handle the image-to-image tasks in the wild. An
enhancement of the efficiency of multiple branches on image-to-image tasks in
the wild will be our next work.

## References

  * Arjovsky et al. (2017) Arjovsky, M., Chintala, S., and Bottou, L.  Wasserstein generative adversarial networks.  In _ICML_ , pp. 214–223, 2017.
  * Bansal et al. (2018) Bansal, A., Ma, S., Ramanan, D., and Sheikh, Y.  Recycle-GAN: Unsupervised video retargeting.  In _ECCV_ , pp. 122–138, 2018.
  * Chan et al. (2018) Chan, C., Ginosar, S., Zhou, T., and Efros, A. A.  Everybody dance now.  _arXiv preprint arXiv:1808.07371_ , 2018.
  * Chen & Tong (2017) Chen, Z. and Tong, Y.  Face super-resolution through Wasserstein GANs.  _arXiv preprint arXiv:1705.02438_ , 2017.
  * Choi et al. (2018) Choi, Y., Choi, M., Kim, M., Ha, J.-W., Kim, S., and Choo, J.  StarGAN: Unified generative adversarial networks for multi-domain image-to-image translation.  In _CVPR_ , pp. 8789–8797, 2018.
  * Durugkar et al. (2017) Durugkar, I., Gemp, I., and Mahadevan, S.  Generative multi-adversarial networks.  In _ICLR_ , 2017.
  * Elson et al. (2007) Elson, J., Douceur, J. R., Howell, J., and Saul, J.  Asirra: a CAPTCHA that exploits interest-aligned manual image categorization.  In _ACM Conference on Computer and Communications Security_ , pp. 366–374, 2007.
  * Gatys et al. (2015) Gatys, L. A., Ecker, A. S., and Bethge, M.  A neural algorithm of artistic style.  _arXiv preprint arXiv:1508.06576_ , 2015.
  * Gokaslan et al. (2018) Gokaslan, A., Ramanujan, V., Ritchie, D., Kim, K. I., and Tompkin, J.  Improving shape deformation in unsupervised image-to-image translation.  In _ECCV_ , pp. 662–678, 2018.
  * Goodfellow et al. (2014) Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y.  Generative adversarial nets.  In _NIPS_ , pp. 2672–2680, 2014.
  * Hardy et al. (2018) Hardy, C., Merrer, E. L., and Sericola, B.  MD-GAN: Multi-discriminator generative adversarial networks for distributed datasets.  _arXiv preprint arXiv:1811.03850_ , 2018.
  * Hosseini-Asl et al. (2018) Hosseini-Asl, E., Zhou, Y., Xiong, C., and Socher, R.  A multi-discriminator CycleGAN for unsupervised non-parallel speech domain adaptation.  In _InterSpeech_ , pp. 3758–3762, 2018.
  * Huang et al. (2018a) Huang, H., Yu, P. S., and Wang, C.  An introduction to image synthesis with generative adversarial nets.  _arXiv preprint arXiv:1803.04469_ , 2018a.
  * Huang & Belongie (2017) Huang, X. and Belongie, S.  Arbitrary style transfer in real-time with adaptive instance normalization.  In _ICCV_ , pp. 1510–1519, 2017.
  * Huang et al. (2018b) Huang, X., Liu, M.-Y., Belongie, S., and Kautz, J.  Multimodal unsupervised image-to-image translation.  In _ECCV_ , pp. 179–196, 2018b.
  * Isola et al. (2017) Isola, P., Zhu, J.-Y., Zhou, T., and Efros, A. A.  Image-to-image translation with conditional adversarial networks.  In _CVPR_ , pp. 5967–5976, 2017.
  * Karras et al. (2018) Karras, T., Aila, T., Laine, S., and Lehtinen, J.  Progressive growing of GANs for improved quality, stability, and variation.  In _ICLR_ , 2018.
  * Kearns & Valiant (1994) Kearns, M. and Valiant, L.  Cryptographic limitations on learning boolean formulae and finite automata.  _Journal of the ACM_ , 41(1):67–95, 1994.
  * Kégl (2013) Kégl, B.  The return of adaboost. mh: multi-class hamming trees.  _arXiv preprint arXiv:1312.6086_ , 2013.
  * Kim et al. (2017) Kim, T., Cha, M., Kim, H., Lee, J., and Kim, J.  Learning to discover cross-domain relations with generative adversarial networks.  In _ICML_ , pp. 1857–1865, 2017.
  * Kingma & Welling (2013) Kingma, D. P. and Welling, M.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Lahiri et al. (2018) Lahiri, A., Jain, A., Nadendla, D., and Biswas, P. K.  Improved techniques for GAN based facial inpainting.  _arXiv preprint arXiv:1810.08774_ , 2018.
  * Learned-Miller et al. (2016) Learned-Miller, E., Huang, G. B., RoyChowdhury, A., Li, H., and Hua, G.  Labeled faces in the wild: A survey.  In _Advances in Face Detection and Facial Image Analysis_ , pp. 189–248. Springer, 2016.
  * Ledig et al. (2017) Ledig, C., Theis, L., Huszár, F., Caballero, J., Cunningham, A., Acosta, A., Aitken, A., Tejani, A., Totz, J., Wang, Z., and Shi, W.  Photo-realistic single image super-resolution using a generative adversarial network.  In _CVPR_ , pp. 105–114, 2017.
  * Lee et al. (2018) Lee, H.-Y., Tseng, H.-Y., Huang, J.-B., Singh, M., and Yang, M.-H.  Diverse image-to-image translation via disentangled representations.  In _ECCV_ , pp. 35–51, 2018.
  * Li (2018) Li, J.  Twin-GAN–unpaired cross-domain image translation with weight-sharing GANs.  _arXiv preprint arXiv:1809.00946_ , 2018.
  * Liu et al. (2015) Liu, Z., Luo, P., Wang, X., and Tang, X.  Deep learning face attributes in the wild.  In _ICCV_ , pp. 3730–3738, 2015.
  * Long et al. (2015) Long, J., Shelhamer, E., and Darrell, T.  Fully convolutional networks for semantic segmentation.  In _CVPR_ , pp. 3431–3440, 2015.
  * Lu (2018) Lu, Y.  Cross domain image generation through latent space exploration with adversarial loss.  _arXiv preprint arXiv:1805.10130_ , 2018.
  * Luo et al. (2015) Luo, Y., Xu, Y., and Ji, H.  Removing rain from a single image via discriminative sparse coding.  In _ICCV_ , pp. 3397–3405, 2015.
  * Mason et al. (2000) Mason, L., Baxter, J., Bartlett, P. L., and Frean, M. R.  Boosting algorithms as gradient descent.  In _NIPS_ , pp. 512–518, 2000.
  * Nilsback & Zisserman (2008) Nilsback, M.-E. and Zisserman, A.  Automated flower classification over a large number of classes.  In _ICVGIP_ , pp. 722–729, 2008.
  * Pathak et al. (2016) Pathak, D., Krahenbuhl, P., Donahue, J., Darrell, T., and Efros, A. A.  Context encoders: Feature learning by inpainting.  In _CVPR_ , pp. 2536–2544, 2016.
  * Reed et al. (2016) Reed, S., Akata, Z., Yan, X., Logeswaran, L., Schiele, B., and Lee, H.  Generative adversarial text to image synthesis.  In _ICML_ , pp. 1060–1069, 2016.
  * Rezende et al. (2014) Rezende, D. J., Mohamed, S., and Wierstra, D.  Stochastic backpropagation and variational inference in deep latent gaussian models.  In _ICML_ , pp. 1278–1286, 2014.
  * Salimans et al. (2016) Salimans, T., Goodfellow, I., Zaremba, W., Cheung, V., Radford, A., and Chen, X.  Improved techniques for training GANs.  In _NIPS_ , pp. 2234–2242, 2016.
  * Schapire (1990) Schapire, R. E.  The strength of weak learnability.  _Machine Learning_ , 5(2):197–227, 1990.
  * Schapire & Freund (2012) Schapire, R. E. and Freund, Y.  _Boosting: Foundations and algorithms_.  MIT press, 2012.
  * Sønderby et al. (2016) Sønderby, C. K., Caballero, J., Theis, L., Shi, W., and Huszár, F.  Amortised map inference for image super-resolution.  _arXiv preprint arXiv:1610.04490_ , 2016.
  * Taigman et al. (2016) Taigman, Y., Polyak, A., and Wolf, L.  Unsupervised cross-domain image generation.  _arXiv preprint arXiv:1611.02200_ , 2016.
  * Tyleček & Šára (2013) Tyleček, R. and Šára, R.  Spatial pattern templates for recognition of objects with regular structure.  In _German Conference on Pattern Recognition_ , pp. 364–374. Springer, 2013.
  * Wang et al. (2018a) Wang, C., Zheng, H., Yu, Z., Zheng, Z., Gu, Z., and Zheng, B.  Discriminative region proposal adversarial networks for high-quality image-to-image translation.  In _ECCV_ , pp. 796–812, 2018a.
  * Wang et al. (2018b) Wang, T.-C., Liu, M.-Y., Zhu, J.-Y., Liu, G., Tao, A., Kautz, J., and Catanzaro, B.  Video-to-video synthesis.  In _NeurIPS_ , 2018b.
  * Wang et al. (2018c) Wang, T.-C., Liu, M.-Y., Zhu, J.-Y., Tao, A., Kautz, J., and Catanzaro, B.  High-resolution image synthesis and semantic manipulation with conditional GANs.  In _CVPR_ , pp. 8798–8807, 2018c.
  * Xudong Mao & Wang (2016) Xudong Mao, Qing Li, H. X. R. Y. L. and Wang, Z.  Multi-class generative adversarial networks with the L2 loss function.  _arXiv preprint arXiv:1611.04076_ , 2016.
  * Yang et al. (2017) Yang, C., Lu, X., Lin, Z., Shechtman, E., Wang, O., and Li, H.  High-resolution image inpainting using multi-scale neural patch synthesis.  In _CVPR_ , pp. 4076–4084, 2017.
  * Yeh et al. (2017) Yeh, R. A., Chen, C., Yian Lim, T., Schwing, A. G., Hasegawa-Johnson, M., and Do, M. N.  Semantic image inpainting with deep generative models.  In _CVPR_ , pp. 5485–5493, 2017.
  * Yi et al. (2017) Yi, Z., Zhang, H., Tan, P., and Gong, M.  DualGAN: Unsupervised dual learning for image-to-image translation.  In _ICCV_ , pp. 2868–2876, 2017.
  * Zhang et al. (2018) Zhang, G., Kan, M., Shan, S., and Chen, X.  Generative adversarial network with spatial attention for face attribute editing.  In _European Conference on Computer Vision_ , pp. 422–437, 2018\.
  * Zhang et al. (2017a) Zhang, H., Sindagi, V., and Patel, V. M.  Image de-raining using a conditional generative adversarial network.  _arXiv preprint arXiv:1701.05957_ , 2017a.
  * Zhang et al. (2017b) Zhang, H., Xu, T., Li, H., Zhang, S., Wang, X., Huang, X., and Metaxas, D.  StackGAN++: Realistic image synthesis with stacked generative adversarial networks.  _arXiv preprint arXiv:1710.10916_ , 2017b.
  * Zhang et al. (2017c) Zhang, H., Xu, T., Li, H., Zhang, S., Wang, X., Huang, X., and Metaxas, D. N.  StackGAN: Text to photo-realistic image synthesis with stacked generative adversarial networks.  In _ICCV_ , pp. 5907–5915, 2017c.
  * Zheng et al. (2018) Zheng, Z., Wang, C., Yu, Z., Zheng, H., and Zheng, B.  Instance map based image synthesis with a denoising generative adversarial network.  _IEEE Access_ , 6:33654–33665, 2018.
  * Zhou (2012) Zhou, Z.-H.  _Ensemble methods: foundations and algorithms_.  Chapman and Hall/CRC, 2012.
  * Zhu et al. (2017) Zhu, J.-Y., Park, T., Isola, P., and Efros, A. A.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _ICCV_ , pp. 2242–2251, 2017.


\intertext{Relations that define a subgroup $\GL_2(-1)$:}
\tag{H:1a}\label{GL2-G-H1H1}
\tag{H:1b}\label{GL2-G-H2H2}
\tag{H:2}\label{GL2-G-H1H2}
%\intertext{Relations that define a subgroup $\GL_2(-1)$:}
\tag{Re:1a}\label{GL2-G-XX}
\tag{Re:1b}\label{GL2-G-YY}
\tag{Re:2}\label{GL2-G-XY}
Y_{-1}(-t)X_{-1}(s)Y_{-1}(t)&= X_{-1}\left(-t^{-1}\right) Y_{-1}\left(-t^{2}s \right)X_{-1}\left(t^{-1} \right),\\
\tag{Re:3}\label{GL2-G-wwH}
\widetilde{w}_{-1}(s)\widetilde{w}_{-1}&=H_1(-s)H_2\left(-s^{-1} \right), \\
\tag{Re:4a}\label{GL2-G-wX}
\widetilde{w}_{-1}X_{-1}(u)\widetilde{w}_{-1}^{-1}&=Y_{-1}(-u),\\
\tag{Re:4b}\label{GL2-G-wY}
\widetilde{w}_{-1}Y_{-1}(u)\widetilde{w}_{-1}^{-1}&=X_{-1}(-u),\\
%\tag{$\GL_2$-G2b}  X_{-1}(-s)Y_{-1}(t)X_{-1}(s) &=Y_{-1}(t), \text{\textcolor{red}{REMOVE}}\\
%\tag{$\GL_2$-G2c}  Y_{-1}(-s)X_{-1}(t)Y_{-1}(s) &=X_{-1}(t), \text{\textcolor{red}{REMOVE}}\\
\tag{Re:5a}\label{GL2-G-wH1}
{\widetilde{w}_{-1}} H_1(s)\widetilde{w}_{-1}^{-1} &= H_2(s),\\
\tag{Re:5b}\label{GL2-G-wH2}
{\widetilde{w}_{-1}} H_2(s)\widetilde{w}_{-1}^{-1} &= H_1(s),\\
\tag{Re:6a}\label{GL2-G-H1X}
\tag{Re:6b}\label{GL2-G-H2X}
H_2(s)X_{-1}(u)H_2(s)^{-1}&=X_{-1}\left(s^{-1}u \right),\\
\tag{Re:6c}\label{GL2-G-H1Y}
H_1(s)Y_{-1}(u)H_1(s)^{-1}&=Y_{-1}\left(s^{-1}u \right),\\
\tag{Re:6d}\label{GL2-G-H2Y}
\intertext{Relations that define subgroups $\GL_2(\ell,j,k)$:}
\tag{Im:1a}\label{G-XX}
\tag{Im:1b}\label{G-YY}
\tag{Im:2}\label{G-XY}
X_{\ell,jk}\left(\frac{-t^{-1}}{c_{\ell j}}\right)Y_{\ell,jk}\left(-c_{\ell j}t^2s\right)X_{\ell,jk}\left(\frac{t^{-1}}{c_{\ell j}}\right),\\
\tag{Im:3}\label{G-wwH}
\widetilde{w}_{\ell,jk}\left(s^{(\ell+1)(j-\ell)} \right)\widetilde{w}_{\ell,jk}&=H_1\left((-s)^{j-\ell}\right) H_2\left((-s)^{\ell+1}\right), \\
\tag{Im:4a}\label{G-wX}
\widetilde{w}_{\ell,jk} X_{\ell,jk}(u) {\widetilde{w}_{\ell,jk}}^{-1}&= Y_{\ell,jk}\left(\frac{-u}{c_{\ell j}}\right),\\
\tag{Im:4b}\label{G-wY}
\widetilde{w}_{\ell,jk} Y_{\ell,jk}(u) {\widetilde{w}_{\ell,jk}}^{-1}&= X_{\ell,jk}\left(-c_{\ell j}u \right),\\
\tag{Im:5a}\label{G-wH1}
\widetilde{w}_{\ell,jk} H_1\left(s^{j-\ell} \right) {\widetilde{w}_{\ell,jk}}^{-1}&=  H_2\left(s^{-(\ell+1)}\right),\\
\tag{Im:5b}\label{G-wH2}
\widetilde{w}_{\ell,jk} H_2\left(s^{\ell+1} \right) {\widetilde{w}_{\ell,jk}}^{-1}&=  H_1\left(s^{-(j-\ell)}\right),\\
\tag{Im:6a}\label{G-H1X}
H_1(s) X_{\ell,jk}(u) H_1(s)^{-1}&=X_{\ell,jk}\left(s^{\ell+1}u \right),\\
\tag{Im:6b}\label{G-H2X}
H_2(s) X_{\ell,jk}(u) H_2(s)^{-1}&=X_{\ell,jk}\left(s^{j-\ell}u \right),\\
\tag{Im:6c}\label{G-H1Y}
H_1(s) Y_{\ell,jk}(u) H_1(s)^{-1}&=Y_{\ell,jk}\left(s^{-(\ell+1)}u \right),\\
\tag{Im:6d}\label{G-H2Y}
H_2(s) Y_{\ell,jk}(u) H_2(s)^{-1}&=Y_{\ell,jk}\left(s^{-(j-\ell)}u \right),\\
\intertext{Relations between the unipotent generators:}
\tag{U:1a}\label{G-X-1X}
(X_{-1}(u), X_{j-1,jk}(v))&=1,\\
\tag{U:1b}\label{G-Y-1Y}
(Y_{-1}(u), Y_{j-1,jk}(v))&=1.\\
\tag{U:1c}\label{G-Y-1X}
(Y_{-1}(u), X_{0,jk}(v))&=1,\\
\tag{U:1d}\label{G-X-1Y}
(X_{-1}(u), Y_{0,jk}(v))&=1,\\
\tag{U:2}\label{G-XYcomm}
(X_{\ell,jk}(u), Y_{m,pq}(v))&=1\qquad\text{for $j\neq p$, $k\neq q$, or $|\ell-m|>1$,}
\intertext{Action of $\widetilde{w}_{-1}$ on the unipotent generators:}
\tag{U:3a}\label{G-w-X}
\widetilde{w}_{-1}X_{\ell,jk}(u)\widetilde{w}_{-1}^{-1}&=X_{j-1-\ell,jk}\left((-1)^{j-\ell-1} u \right), \\
\tag{U:3b}\label{G-w-Y}
\widetilde{w}_{-1}Y_{\ell,jk}(u)\widetilde{w}_{-1}^{-1}&=Y_{j-1-\ell,jk}\left((-1)^{j-\ell-1} u \right),
\end{align*}
\begin{longver}
\begin{align*}
\tag{U:4a}\label{GL2-G-Yelim}
Y_{-1}(s)& =X_{-1}\left(s^{-1} \right)H_1 \left(-s^{-1} \right)H_2 \left(-s \right)\widetilde{w}_{-1}X_{-1} \left(s^{-1} \right).\\
\tag{U:4b}\label{G-Yelim}
Y_{\ell,jk}(s) &=
X_{\ell,jk}\left(\frac{ s^{-1}}{c_{\ell j}}\right)
H_1\left(\left[-{{c_{\ell j}}}s\right]^{-1/(\ell+1)}\right)
H_2\left(\left[-{{c_{\ell j}}}s\right]^{-1/(j-\ell)}\right)w_{\ell,jk}X_{\ell,jk}\left(\frac{ s^{-1}}{c_{\ell j}}\right).
\end{align*}
\end{longver}
\endgroup
We now define $G(\mathfrak{m})$ as the group given by this presentation, that is,
$${G}(\mathfrak{m})= \left\langle \mathcal{X}\mid \mathcal{R}\right\rangle={F}(\mathcal{X})/N_\mathcal{R},$$
where $N_\mathcal{R}$ is the normal closure of the relations $\mathcal{R}$.
\end{defn}

%[This is not strictly speaking true]
%Note that  $\widetilde{w}_{-1}$ acts on all the  generators of $G(\frak m)$  but $ \widetilde{w}_{\ell,jk}$ only acts on  $X_{\ell,jk}$ and $Y_{\ell,jk}$.

We do not claim that this presentation is  minimal -- some of the relations
follow from the other relations but are included for their usefulness.

\begin{defn}\label{subgps} We define the following subgroups  of $G(\mathfrak{m})$:
\begin{align*}
\GL_2(-1) &:= \langle X_{-1}(u), Y_{-1}(u), H_1(s), H_2(s)\mid u\in\C,\,s\in\C^\times\rangle,\\
\GL_2(\ell,j,k) &:= \langle X_{\ell,jk}(u), Y_{\ell,jk}(u), H_1(s), H_2(s)\mid u\in\C,\,s\in\C^\times\rangle \qquad\text{for $(\ell,j,k)\in E$,}\\
\Pp &:= \left\langle \GL_2(-1), X_{\ell,jk}(u) \mid (\ell,j,k)\in E,\,u\in\C\right\rangle,\\
\Pm &:= \left\langle \GL_2(-1), Y_{\ell,jk}(u) \mid  (\ell,j,k)\in E,u\in\C\right\rangle,\\
U_{\ell,jk;\,m,pq} &:= \left\langle X_{\ell,jk}(u), Y_{m,pq}(u) \mid u\in\C\right\rangle\qquad\text{for distinct $(\ell,j,k),\,(m,p,q)\in E$}.
\end{align*}
\end{defn}
%where $\Pi$ is a positive root system as defined in Subsection~\ref{SS-pos}.

\begin{corollary} $\;$\label{C-comm}
The following relations hold in every $\widehat{U}^{\,\Pi}$ in which the elements involved are defined:
\begin{enumerate}
\item \eqref{GL2-G-XX},  \eqref{GL2-G-YY}, \eqref{G-XX}, \eqref{G-YY};
\item $\left(X_{-1}(u),X_{j-1,jk}(v)\right) = \left(Y_{-1}(u),Y_{j-1,jk}(v)\right) = 1$, ie, \eqref{G-X-1X} and \eqref{G-Y-1Y};
\item $\left(X_{-1}(u),Y_{0,jk}(v)\right) = \left(Y_{-1}(u),X_{0,jk}(v)\right) = 1$, ie, \eqref{G-X-1Y} and \eqref{G-Y-1X};
\item $\left(X_{\ell,jk}(u),Y_{m,pq}(v)\right) =1$ for $j\ne p$, $k\ne q$, or $\left|\ell-m\right|>1$.ie, \eqref{G-XYcomm}.
\end{enumerate}
\end{corollary}

We can now show that $\GL_2(-1)$ satisfies the relations given in Definition~\ref{Defn} for this subgroup. To be precise:
\begin{lemma}\label{L-GL2-1}
The group $\GL_2({-1})\subseteq \Aut(\mathfrak{m})$ has generators
$H_1(s), H_2(s), X_{-1}(u),  Y_{-1}(u)$ for  $s\in\C^\times,\,u\in\C $,
and defining relations \eqref{GL2-G-H1H1}, \eqref{GL2-G-H2H2}, \eqref{GL2-G-H1H2}, \eqref{GL2-G-XX},
\eqref{GL2-G-YY}, \eqref{GL2-G-XY}, \eqref{GL2-G-wwH}, \eqref{GL2-G-wX}, \eqref{GL2-G-wY}, \eqref{GL2-G-wH1},
\eqref{GL2-G-wH2}, \eqref{GL2-G-H1X}, \eqref{GL2-G-H2X}, \eqref{GL2-G-H1Y}, and \eqref{GL2-G-H2Y}.
\end{lemma}

\begin{longver}
\begin{proof} These follow from the corresponding relations \eqref{GL2-H1H1}, \eqref{GL2-H2H2}, \eqref{GL2-H1H2}, \eqref{GL2-XX},
\eqref{GL2-YY}, \eqref{GL2-XY}, \eqref{GL2-wwH}, \eqref{GL2-wX}, \eqref{GL2-wY}, \eqref{GL2-wH1},
\eqref{GL2-wH2}, \eqref{GL2-H1X}, \eqref{GL2-H2X}, \eqref{GL2-H1Y}, and \eqref{GL2-H2Y}.
\end{proof}
\end{longver}

We can now show that each $\GL_2(\ell,j,k)$ satisfies the relations given in Definition~\ref{Defn} which involve the generators of $\GL_2(\ell,j,k)$.
\begin{lemma}\label{L-GL2ljk}
The group $\GL_2({\ell,j,k})\subseteq\Aut(\mathfrak{gl}_2(\ell,j,k))$ has generators
$H_1(s), H_2(s), X_{\ell,jk}(u),  Y_{\ell,jk}(u)$ for  $s\in\C^\times,\,u\in\C $,
and defining relations \eqref{GL2-G-H1H1}, \eqref{GL2-G-H2H2}, \eqref{GL2-G-H1H2}, \eqref{G-XX},
\eqref{G-YY}, \eqref{G-XY}, \eqref{G-wwH}, \eqref{G-wX}, \eqref{G-wY}, \eqref{G-wH1},
\eqref{G-wH2}, \eqref{G-H1X}, \eqref{G-H2X}, \eqref{G-H1Y}, and \eqref{G-H2Y}.
\end{lemma}
\begin{proof}
Now \eqref{G-XX} is equivalent to \eqref{GL2-XX};
\eqref{G-YY} is equivalent to \eqref{GL2-YY} with substitutions $u\to c_{\ell j} u$, $v\to c_{\ell j} v$;
\eqref{G-wwH} is equivalent to \eqref{GL2-wwH};
\eqref{G-XY} is equivalent to \eqref{GL2-XY} with substitution $t\to c_{\ell j} t$;
\eqref{G-wH1} is equivalent to \eqref{GL2-wH1};
\eqref{G-wH2} is equivalent to \eqref{GL2-wH2};
\eqref{G-wX} is equivalent to \eqref{GL2-wX};
\eqref{G-wY} is equivalent to \eqref{GL2-wY} with substitution $u\to c_{\ell j} u$.

\eqref{GL2-H1X}  is equivalent to
\begin{align*}
{H}_1\left(t^{1/(\ell+1)} \right)X_{\ell,jk}\left(u \right){H}_1\left(t^{-1/(\ell+1)} \right)&=X_{\ell,jk}(tu),
\end{align*}
which gives \eqref{G-H1X} in the particular case where $s=t^{\ell+1}$ and $\left(t^{\ell+1} \right)^{1/(\ell+1)}=t$ for our chosen branch of the logarithm.
When $\left(t^{\ell+1} \right)^{1/(\ell+1)}\ne t$,  \eqref{G-H1X} is a redundant equation that also holds in  $\GL_2({\ell,j,k})$.
Note that these redundant equations ensure that this relation is independent of the chosen  branch of logarithm.
Similar arguments give
\eqref{G-wwH} from \eqref{GL2-wwH} with substitution $s\to s^{(\ell+1)(j-\ell)}$;
\eqref{G-H1Y} from \eqref{GL2-H1Y} with substitutions $u\to c_{\ell j} u$, $s\to s^{\ell+1}$;
\eqref{G-H2X} from \eqref{GL2-H2X}  with substitution $s\to s^{j-\ell}$; and
\eqref{G-H2Y} from \eqref{GL2-H2Y} with substitutions $u\to c_{\ell j} u$, $s\to s^{j-\ell}$.
%and \eqref{G-Yelim} from \eqref{GL2-Yelim} with substitution $s\to c_{\ell j}s$.
\end{proof}

It   now follows that $\Phpm$ satisfies the relations given in Definition~\ref{Defn} for this subgroup,
other than the commutator relations that are covered by Corollary~\ref{C-comm}.
\begin{corollary} The relations
\eqref{G-H1X}, \eqref{G-H2X}, and \eqref{G-wX} in $G(\frak m)$ hold in $\Php$ and
\eqref{G-H1Y}, \eqref{G-H2Y}, and \eqref{G-wY} hold in $\Phm$.
\end{corollary}

In conclusion, we have  shown that each relation in Definition~\ref{Defn} holds in whichever of the groups
$\GL_2(-1)\subseteq\Aut(\mathfrak{m})$, $\GL_2(\ell,j,k)\subseteq\Aut(\gl_2(\ell,j,k))$, $\widehat{{P}}^+\subseteq\Aut(\mhat)$, $\widehat{{P}}^-\subseteq\Aut(\mhat^-)$,  or
$\UhPi\subseteq\Aut(\widehat{\frak m}^\Pi)$ contains all the
generators that appear in that relation.
%These subgroups are used to  justify the definition of $G(\mathfrak{m})$ in the following sections.
Even though $G(\frak m)$ is not a group of automorphisms of $\frak m$,
each of these subgroups corresponds to a group contained in $\Aut(\mathfrak{L})$, where
$\mathfrak{L}$ is either $\mathfrak{m}$, or some $\gl_2$ subalgebra of $\mathfrak{m}$, or some completion of $\mathfrak{m}$.
In particular, we have constructed a group $\GL_2(-1)$ acting as automorphisms of $\mathfrak{m}$,
groups $\GL_2(\ell,j,k)$ acting as automorphisms on $\gl_2(\ell,j,k)$ %:=\C f_{\ell,jk}\oplus \mathfrak{h} \oplus \C e_{\ell,jk}$ that correspond to
and incomplete subgroups of $\Ppm$ and $U_{\ell,jk;\,m,pq}$ acting as automorphisms of various completions of $\mathfrak{m}$.
For each of the subgroups $\GL_2(-1), \GL_2(\ell,j,k), \Ppm$, and $ U_{\ell,jk;\,m,pq}$ of $G(\mathfrak{m})$ we have shown %(Sections~\ref{PositiveRootSys} and ~\ref{S-related}
that  the relations from Definition~\ref{Defn} involving the generators of the subgroup hold in the corresponding automorphism group $\Aut(\mathfrak{L})$.
% This shows that each of these subgroups of $G(\m)$ is a quotient of the corresponding group $\Aut(\mathfrak{t})$ of automorphisms.
We conjecture (see [3]) that each subgroup $\GL_2(-1), \GL_2(\ell,j,k), \Ppm$ and $ U_{\ell,jk;\,m,pq}$ of $G(\mathfrak{m})$ is actually isomorphic to the corresponding group of automorphisms in $\Aut(\mathfrak{L})$, and that $G(\m)$ can be described as an amalgam of these groups.% of $\mathfrak{t}$ and hence is a trivial quotient of $\Aut(\mathfrak{t})$ (see [3]).

%{\color{blue} There is also a proper subgroup $\mathfrak{G}(\frak m)$ of $G(\frak m)$ (with smaller unipotent subgroups) generated by $\frak{gl}_2$ and the  imaginary simple roots. That is, consider the group generated by  $e_{\ell,jk}$,  $f_{\ell,jk}$ with $\ell=0$ and the simple roots $\a_{jk}$ (that is, $(1,j)\in II_{1,1}$). Certain relations go away when $\ell=0$. Other relations involve indices of the form $j-1-\ell$, but this index becomes $j-1$ and these relations still make sense.}

\bibliographystyle{amsalpha}
\newcommand{\etalchar}[1]{$^{#1}$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
\href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{ACJM23b}

[1]
Darlayne Addabbo, Lisa Carbone, Elizabeth Jurisich, Maryam Khaqan, and Scott~H.
Murray, \emph{A monstrous lie group}, In preparation (2023).

[2]
Abid Ali, Lisa Carbone, Elizabeth Jurisich, and Scott~H. Murray, \emph{Complete
pro-unipotent groups for {B}orcherds {K}ac--{M}oody algebras}, In preparation

[3]
\bysame, \emph{A group amalgam for the {M}onster {L}ie algebra}, In preparation

[4]
Richard~E. Borcherds, \emph{Vertex algebras, {K}ac-{M}oody algebras, and the
{M}onster}, Proc. Nat. Acad. Sci. U.S.A. \textbf{83} (1986), no.~10,
3068--3071. \MR{843307}

[5]
Richard Borcherds, \emph{Generalized {K}ac-{M}oody algebras}, J. Algebra
\textbf{115} (1988), no.~2, 501--512. \MR{943273}

[6]
Richard~E. Borcherds, \emph{Monstrous moonshine and monstrous {L}ie
superalgebras}, Invent. Math. \textbf{109} (1992), no.~2, 405--444.
\MR{1172696}

[7]
\bysame, \emph{The fake {M}onster formal group}, Duke Math. J. \textbf{100}
(1999), no.~1, 139--165. \MR{1714758}

[8]
Lisa Carbone, Elizabeth Jurisich, and Scott~H. Murray, \emph{Constructing a
{L}ie group analog for the {M}onster {L}ie algebra}, Lett. Math. Phys.
\textbf{112} (2022), no.~3, No. 43, 16. \MR{4418318}

[9]
J.~H. Conway and S.~P. Norton, \emph{Monstrous moonshine}, Bull. London Math.
Soc. \textbf{11} (1979), no.~3, 308--339. \MR{554399}

[10]
John~Horton Conway and Neil James~Alexander Sloane, \emph{Sphere packings,
lattices and groups}, vol. 290, Springer Science \& Business Media, 2013.

[11]
Igor Frenkel, James Lepowsky, and Arne Meurman, \emph{Vertex operator algebras
and the {M}onster}, Pure and Applied Mathematics, vol. 134, Academic Press,
Inc., Boston, MA, 1988. \MR{996026}

[12]
P.~Goddard and C.~B. Thorn., \emph{Compatibility of the dual pomeron with
unitarity and the absence of ghosts in the dual resonance model}, Phys.
Lett., B \textbf{40} (1972), no.~2, 235--238.

[13]
Jeffrey~A. Harvey and Gregory Moore, \emph{Algebras, {BPS} states, and
strings}, Nuclear Phys. B \textbf{463} (1996), no.~2-3, 315--368.
\MR{1393643}

[14]
E.~Jurisich, J.~Lepowsky, and R.~L. Wilson, \emph{Realizations of the {M}onster
{L}ie algebra}, Selecta Math. (N.S.) \textbf{1} (1995), no.~1, 129--161.
\MR{1327230}

[15]
Elizabeth Jurisich, \emph{An exposition of generalized kac-moody algebras},
Contemporary Mathematics \textbf{194} (1996), 121--160.

[16]
\bysame, \emph{Generalized {K}ac-{M}oody {L}ie algebras, free {L}ie algebras
and the structure of the {M}onster {L}ie algebra}, J. Pure Appl. Algebra
\textbf{126} (1998), no.~1-3, 233--266. \MR{1600542}

[17]
Seok-Jin Kang, \emph{Ringel-{H}all algebra construction of quantum
{B}orcherds-{B}ozec algebras}, J. Algebra \textbf{498} (2018), 344--361.
\MR{3754419}

[18]
Shrawan Kumar, \emph{Kac-moody groups, their flag varieties and representation
theory}, vol. 204, Springer Science \& Business Media, 2012.

[19]
\bysame, \emph{Subalgebra generated by ad-locally nilpotent elements of
{B}orcherds generalized {K}ac-{M}oody {L}ie algebras}, J. Algebra
\textbf{594} (2022), 307--312. \MR{4353239}

[20]
James Lepowsky and Haisheng Li, \emph{Introduction to vertex operator algebras
and their representations}, Progress in Mathematics, vol. 227, Birkh\"{a}user
Boston, Inc., Boston, MA, 2004. \MR{2023933}

[21]
Ottmar Loos and Erhard Neher, \emph{Reflection systems and partial root
systems}, Walter de Gruyter GmbH \& Co. KG, 2011.

[22]
Jun Morita, \emph{Roots of {K}ac--{M}oody lie algebras}, Tsukuba Journal of
Mathematics \textbf{4} (1980), no.~2, 349--354.

[23]
Robert~V. Moody and Arturo Pianzola, \emph{Lie algebras with triangular
decompositions}, Canadian Mathematical Society Series of Monographs and
Advanced Texts, John Wiley \& Sons Inc., New York, 1995, A Wiley-Interscience
Publication. \MR{96d:17025}

[24]
James Munkres, \emph{Topology}, 2 ed., Pearson, New York, 1999.

[25]
N.~M. {Paquette}, D.~{Persson}, and R.~{Volpato}, \emph{{Monstrous BPS-Algebras
and the Superstring Origin of Moonshine}}, ArXiv e-prints (2016).

[26]
Guy Rousseau, \emph{Almost split {K}ac--{M}oody groups over ultrametric
fields}, arXiv preprint arXiv:1202.6232 (2012), 1--58.

[27]
AI~Shirshov, \emph{On the bases of a free {L}ie algebra}, Selected Works of AI
Shirshov, Springer, 2009, pp.~113--118.

[28]
T.~A. Springer, \emph{Linear algebraic groups}, second ed., Modern
Birkh\"{a}user Classics, Birkh\"{a}user Boston, Inc., Boston, MA, 2009.
\MR{2458469}

[29]
Shlomo Sternberg, \emph{Lie algebras}, University Press, Florida, 2004.

[30]
Robert Steinberg, \emph{Lectures on {C}hevalley groups}, University Lecture
Series, vol.~66, American Mathematical Society, Providence, RI, 2016.

[31]
J.~G. Thompson, \emph{Some numerology between the {F}ischer-{G}riess {M}onster
and the elliptic modular function}, Bull. London Math. Soc. \textbf{11}
(1979), no.~3, 352--353. \MR{554402}

[32]
Jacques Tits, \emph{R\'{e}sum\'{e}s des cours au {C}oll\`ege de {F}rance 1981},
Documents Math\'{e}matiques (Paris) [Mathematical Documents (Paris)],
Soci\'{e}t\'{e} Math\'{e}matique de France, Paris, 1981. \MR{3235648}

[33]
\bysame, \emph{Uniqueness and presentation of {K}ac-{M}oody groups over
fields}, J. Algebra \textbf{105} (1987), no.~2, 542--573. \MR{873684}

\end{thebibliography}

\end{document}

% Moved to part II

\section{The amalgam}\label{amalgam}
The group $G(\mathfrak{m})$ can now be constructed as an amalgam of groups, each of which acts as automorphisms on a subalgebra or completion of $\mathfrak{m}$.
\begin{defn}
$\mathcal{A}(\mathfrak{m})$ is the collection of groups consisting of
\begin{enumerate}
\item\label{Am-Uim} $M\ltimes\Uimp\subseteq\Aut\left(\mhat\right)$ and $M\ltimes\Uimm\subseteq\Aut\left(\mhat^-\right)$;
\item\label{Am-2param} $\left\langle U^\epsilon_{-1}, \, U^\delta_{\ell,jk} \right\rangle\subseteq\Aut\left(\mhat^\Pi\right)$ when $\epsilon,\delta\in\{+,-\}$
and $\epsilon\a_{-1},\delta\a_{\ell,jk}\in\Pi$;\\
$\left\langle \Upm_{\ell,jk}, \, U^\mp_{m,pq} \right\rangle\subseteq\Aut\left(\mhat^\Pi\right)$ when $\pm\a_{\ell,jk},\mp\a_{m,pq}\in\Pi$;
\item\label{Am-1param} $\Upm_{\ell,jk}\subseteq\Aut\left(\gl_2(\ell,j,k)\right)$ or $\subseteq\Aut\left(\mhat^\Pi\right)$ when $\a_{\ell,jk}\in\Pi$;
\item\label{Am-GL2im} $\GL_2(\ell,j,k)\subseteq\Aut\left(\gl_2(\ell,j,k)\right)$;
\item\label{Am-GL2re} $1,H,M, \Upm_{-1}, \GL_2(-1)\subseteq\Aut(\m)$;
\end{enumerate}
for distinct $(\ell,j,k),(m,p,q)\in E$.
\end{defn}

We now need to define the intersections in this amalgam.
The complication is that the groups are defined over different Lie algebras, however we can define intersections
in analogy with the Kac--Moody case.
\begin{description}
\item[\eqref{Am-Uim} and \eqref{Am-Uim}]
We take
$$\left(M\ltimes\Uimp\right)\cap \left(M\ltimes \Uimm\right)= M$$
by definition.
For group in () with one in (), consider the example of $\GL_2(\ell,j,k)\subseteq\Aut\left(\gl_2(\ell,j,k)\right)$ and
$\langle \Up_{\ell,jk}, \, \Up_{m,pq} \rangle\subseteq\Aut\left(\mhat^\Pi\right)$ whose intersection taken to be $\Up_{\ell,jk}$, which can be considered
as a subgroup of either automorphism group.

\item[\eqref{Am-2param} and \eqref{Am-2param}] Suppose we have distinct $(\ell,j,k),(m_1,p_1,q_1) ,(m_2,p_2,q_2)\in E$ and $\epsilon,\delta_1,\delta_2\in\{+,-\}$ so that
for some positive root system $\Pi$. Then Propositions~\ref{P-2paramcartprod} and~\ref{P-2paramfreeprod}  imply that
$$\left\langle U^{\epsilon}_{\ell,jk}, U^{\delta_1}_{m_1,p_1q_1} \right\rangle \cap \left\langle U^{\epsilon}_{\ell,jk}, U^{\delta_1}_{m_2,p_2q_2} \right\rangle
= U^{\epsilon}_{\ell,jk}.$$
On the other hand, if there is no positive root system containing $\epsilon\a_{\ell,jk},\epsilon_1\a_{m_1,p_1q_1},\epsilon_2\a_{m_2,p_2q_2}$, we take this intersection to be true by definition. Similarly we can take
$$\left\langle U^{\epsilon_1}_{\ell_1,j_1k_1}, U^{\delta_1}_{m_1,p_1q_1} \right\rangle
\cap \left\langle U^{\epsilon_2}_{\ell_2,j_2k_2}, U^{\delta_2}_{m_2,p_2q_2} \right\rangle
= 1.$$
whenever we have distinct $(\ell_1,j_1,k_1),(\ell_2,j_2,k_2),(m_1,p_1,q_1) ,(m_2,p_2,q_2)\in E$ and
$\epsilon_1, \epsilon_2,\delta_1,\delta_2\in\{+,-\}$ Intersections involving $\left\langle U^\epsilon_{-1}, \, U^\delta_{\ell,jk} \right\rangle$ are similar.

\item[\eqref{Am-Uim}--\eqref{Am-1param} and \eqref{Am-1param}--\eqref{Am-GL2im}]  Sim.

\item[\eqref{Am-Uim}--\eqref{Am-GL2re} and \eqref{Am-GL2re}] A subgroup of $\Aut(\m)$ can easily be
extended to act on $\mhat^\Pi$, for any positive root system $\Pi$, or restricted to act on  $\gl_2(\ell,j,k)$. So it is easy to determine intersections involving a group in~\eqref{Am-GL2re}.
\end{description}

It is now easily checked that $\mathcal{A}(\mathfrak{m})$ is closed under intersections and thus it is an amalgam.
Recall that $G(\frak m)=\left\langle \mathcal{X}\mid \mathcal{R}\right\rangle$, where $\mathcal{X}$ and $\mathcal{R}$ are given by  Definition~\ref{Defn}.
We have shown that each group in $\mathcal{A}(\mathfrak{m})$ has a presentation consisting of the relevant
generators from $\mathcal{X}$ and the relations in $\mathcal{R}$ that contain only those generators
(Lemma~\ref{L-GL2-1}, Lemma~\ref{L-GL2ljk}, Lemma~\ref{L-embedding},
Proposition~\ref{P-MUimp}, Corollary~\ref{C-MUimm}
Proposition~\ref{P-2paramcartprod}, and Proposition~\ref{P-2paramfreeprod}).
So we have proved:
\begin{theorem}
$G(\frak m)$ is the group of the amalgam $\mathcal{A}(\mathfrak{m})$.
\end{theorem}

%\section{Campbell-Baker-Hausdorff formula and group commutators}\label{SS-comm}
%We now  form the completion  $\widehat{L}(S)$ of $L(S)$ using the grading  $L(S)=\oplus_{n\geq 1}L_n(S)$, where $L_n(S)$ is the homogeneous component of degree $n$ in $L(S)$.
%That is,  $L_n(S)$ is the linear span of Lie monomials of degree $n$ in $L(S)$.
%$$\widehat{L}(S)=\left\{\sum_{n=1}^\infty a_n\mid a_n\in L_n(S),\ n=1,2,\dots \right\}$$
%\begin{theorem} ([Bahturin], p 286) $\exp(\widehat{L}(S))$ is a subgroup of $\mathcal{M}(S)$.
%{\color{blue} For $x\in \widehat{L}(S)$, we write $\exp(x)$ for the corresponding element of $\mathcal{M}(S)$. As an element of $\Aut(\widehat{m})$, this element is written as $\exp(\ad(x))$.}
%By [Sternberg], for any $x$, $y$ in $\widehat{L}(S)$, there exists $z$ in $\widehat{L}(S)$ satisfying
%$$\exp z = (\exp x)(\exp y)$$
%given by the formula
%$$z= x+y+\frac{1}{2}[x,y]+\frac{1}{12}([x,[x,y]]-[y,[x,y]])+\cdots.$$
%This gives a Campbell-Baker-Hausdorff formula for $x,y\in \widehat{L}(S)$ [29][Section 1.12]:
%$$(\exp x)(\exp y)= \exp\left(x+y+\frac{1}{2}[x,y]+\frac{1}{12}([x,[x,y]]-[y,[x,y]])+\cdots \right).$$
%The right hand side may be indexed over all positive linear combinations of roots that are roots. The product is taken with respect to an ordering on the set of roots consistent with height.
% Thus the
%Campbell-Baker-Hausdorff formula gives group commutator in the image $\exp(\widehat{L}(S))\leq \mathcal{M}(S)$, for  $x$, $y$ in $\widehat{L}(S)$.
%\begin{lemma}\label{BCHcomm} For $x,y\in\widehat{L}(S)$, $s,t\in\C$, the Campbell-Baker-Hausdorff formula gives rise to group commutator
%(\exp(sx),\exp(ty))&=\exp\left(c_{1,1}st[x,y]+c_{2,1}s^2t[x,[x,y]]+c_{1,2}st^2[y,[x,y]])\right. \\
%&\qquad\left. +c_{3,1}s^3t[x,[x,[x,y]]]+c_{2,2}s^2t^2[y,[x,[x,y]]]+\cdots \right)
%where $c_{i,j}\in\Q$.
%\begin{proof} Applying the Campbell-Baker-Hausdorff formula to $\exp(sx)\exp(ty)$ and $\exp(ty)\exp(sx)$, we obtain
%\exp(sx)\exp(ty)&=\exp(ty)\exp(sx)\exp\left(c_{1,1}st[x,y])+c_{2,1}s^2t[x,[x,y]]+c_{1,2}st^2[y,[x,y]])\right. \\
%&\qquad \left.+c_{3,1}s^3t[x,[x,[x,y]]]+c_{2,2}s^2t^2[y,[x,[x,y]]]+\cdots \right).
%This is an infinite dimensional analog of Chevalley's group commutation formula ([St]) where  the coefficients $c_{i,j}$ can be found in $\Z$, using a more elaborate argument.


# Pre-Sorted Tsetlin Machine
(The Genetic K-Medoid Method)

Jordan Morris Jordan Morris was with the $\mu$Systems design group, Newcastle
University, Newcastle, NE1 7RU . He is now CEO of Bitset Technologies.
E-mail<EMAIL_ADDRESS>-<EMAIL_ADDRESS>
###### Abstract

This paper proposes a machine learning pre-sort stage to traditional
supervised learning using Tsetlin Machines. Initially, N data-points are
identified from the dataset using an expedited genetic algorithm to solve the
maximum dispersion problem. These are then used as the initial placement to
run the K-Medoid clustering algorithm. Finally, an expedited genetic algorithm
is used to align N independent Tsetlin Machines by maximising hamming
distance. For MNIST level classification problems, results demonstrate up to
10% improvement in accuracy, $\mathtt{\sim}$383X reduction in training time
and $\mathtt{\sim}$86X reduction in inference time.

###### Index Terms:

B.6.0.Logic Design, B.7.0.Integrated Circuit Design, C.1.0.Processor
Architectures, I.2.6.Artificial Intelligence - Learning

##  1 Introduction

The recent surge in neural network-based machine learning and artificial
intelligence has propelled many in the field to revisit more traditional
learning methodologies. Many of these offer simpler feedback mechanisms and
simpler primitives than the perceptron. This often translates into simpler
hardware and faster software.
One architecture to gain significant traction is the Tsetlin Machine [1],
which is based on propositional logic and uses Tsetlin Automata to identify
common sub-patterns in binarized data from a given entropy. Instead of
backpropagation using stochastic gradient decent to optimize biases and
weights, Tsetlin Machine employs a game-theoretic feedback mechanism that
optimises for Nash equilibria.
Whilst the Tsetlin Machine is a capable algorithm, much of the computation
time is spent focusing on outliers within the data [2], for which, more
computationally-efficient handling exists. This paper therefore investigates
how the training times, inference times and accuracy of the Tsetlin Machine
are impacted when datasets are pre-sorted. Specifically, the contributions of
this paper are:-

  * •

Using an expedited genetic algorithm to ”conceptually arrange” the binarized
datasets and identify N datapoints that provide the maximum dispersion based
on hamming distance.

  * •

Using the K-Medoid clustering algorithm to sort same-class datapoints into N
clusters based on hamming distance.

  * •

Using an expedited genetic algorithm to align the newly-formed clusters into N
independent Tsetlin Machines.

  * •

An evaluation of how this pre-sorting methodology impacts the accuracy,
training time and inference time for MNIST level classification problems.

  * •

A discussion on how the outlined stages may be optimised in hardware.

This paper consists of 7 sections. Section 2 provides a brief overview of the
Tsetlin Machine. Section 3 details the proposed pre-sort architecture. Section
4 delineates the experiment methodologies. Section 5 presents the results.
Section 6 discusses how such improvments in accuracy and performance are
achieved. Section 7 concludes the paper.

##  2 Tsetlin Machine

An exhaustive description of the Tsetlin Machine, complete with formal
mathematical derivation of the game theoretic feedback mechanism, may be found
in the seminal paper [1]. To aid the reader, a brief description of the key
features of the algorithm are provided here.

###  2.1 Tsetlin Automata

The Tsetlin Automaton provides the elementary primitive for the Tsetlin
Machine algorithm. In it’s most basic form, the Tsetlin Automaton is simply a
linear state machine consisting of N states, upon which, actions may be taken
to change the current state. An example of a Tsetlin Automata with N=6 may be
seen in Figure 1.

Figure 1: Tsetlin Automaton

The N states are split into two equal regions, ”Exclude” and ”Include”. These
represent whether or not a particular bit should be included in a given sub-
pattern. Feedback to the automaton may be provided in the form of two actions:
Reward, Penalty. A reward action indicates that the feedback mechanism
suspects that the current state of the automaton falls within the correct
include/exclude region. The reward action therefore reinforces the current
decision by pushing the current state of the automaton further away from the
include/exclude boundary. A penalty action indicates that the feedback
mechanism suspects that the current state of the automaton falls within the
incorrect region. The penalty action therefore weakens the current decision by
pushing the current state of the automaton towards the include/exclude
boundary. If the state was already on the include/exclude boundary when the
penalty action was received, the boundary is traversed and the decision on
whether the particular bit represented by the automaton is included or
excluded is changed accordingly.

###  2.2 Clauses

One Tsetlin Automaton is used to represent each bit in the binarized input
feature (F). An additional Tsetlin Automaton is used to represent the negated
value of each bit in the binarized input feature. These are commonly referred
to as literals (L). Hence L = 2F. A clause with F=3 (L=6) may be seen in
Figure 2.

The figure shows two automata with include decisions and four automata with
exclude decisions. The subpattern created by this clause is
$\\{X_{2},\overline{X}_{1}\\}$. Only the two included bits of the input
feature shall be checked (both $X_{3}$ and $\overline{X}_{3}$ are excluded).
The clause shall become active if the first bit in the feature is zero
($\overline{X}_{1}$) and the second bit in the feature is one ($X_{2}$). For
all other combinations of the first two bits of the input feature, the clause
shall become inactive.

###  2.3 Tsetlin Machine Architecture

The basic structure of a Tsetlin Machine is dependent on the number of classes
required for the dataset. For two classes, a simple mono structure is
sufficient. For three or more classes, a slightly more sophisticated multi-
class structure is required.

####  2.3.1 Mono Tsetlin Machine Architecture

A high level depiction of the mono Tsetlin Machine architecture may be seen in
Figure 3.

Clauses (C) are instantiated as ”clause-pairs”, with one assigned a positive
polarity and one assigned a negative polarity. Assuming a dataset of two
classes (Class 0 and Class 1), the negative clauses may be assigned to Class 0
and the positive clauses to Class 1. A datapoint is distributed to all clauses
in a single action. If a clause is active, it votes with its polarity (+1/-1).
If it is inactive, it does not vote (and therefore has no impact on further
calculations). These positive and negative votes are accumulated into a class
sum (CS). A simple threshold is then applied to the class sum. If the class
sum is below the threshold, the predicted class is Class 0. If the class sum
is above the threshold, the predicted class is Class 1.

Figure 2: Tsetlin Machine Clause Figure 3: Mono Tsetlin Machine Architecture
Figure 4: Multi-Class Tsetlin Machine Architecture

####  2.3.2 Multi-Class Tsetlin Machine Architecture

For three or more classes, the mono Tsetlin Machine architecture is repeated,
one for each class, and the thresholding is replaced with an argmax. A high
level depiction of a 3-class Tsetlin Machine may be seen in Figure 4.

In this instance, the binarized input feature is distributed to all clauses,
the three class sums are calculated and the largest class sum becomes the
predicted class.

##  3 Pre-Sort Architecture

The proposed pre-sort architecture can be split into three distinct stages:
Binary Maximum Dispersion (M), Binary K-Medoid (K) and Genetic Class Alignment
(G). These stages are run sequentially on the dataset. The result is a rapid
sorting of data that may be split into N data subsets that are then
distributed to smaller Tsetlin Machines. A high level overview of the pre-sort
architecture may be seen in Figure 5.

###  3.1 Binary Maximum Dispersion

The purpose of this stage is to identify N datapoints within each class of the
dataset that represent the maximum cumulative difference possible. This is
commonly referred to as solving the maximum dispersion problem. For binarized
datasets, there is usually no ordinality (one handwritten digit isn’t
inherently greater or lesser than another). However, a ”distance” between two
binarized datapoints can be measured using the hamming distance (the number of
bits different between them). In this manner, the N maximally-distant
datapoints may be identified and the remaining data ”conceptually arranged” by
hamming distance between them. A visualiation of this process for N=8
datapoints may be seen in Figure 6.

To find the datapoints, an expedited genetic algorithm is used to determine
the greatest cumulative hamming distance between N chosen datapoints. The
final N datapoints need only be a rough estimate at this stage as they are
updated by the next stage. The genetic algorithm therefore does not require
execution until exhaustion and can be parallelized to further reduce run time.

###  3.2 Binary K-Medoid Algorithm

The Binary K-Medoid Algorithm performs the bulk of the work in the pre-sort
architecture. Unlike the more common K-Means clustering algorithm, K-Medoid
chooses an actual datapoint to cluster on. This makes the algorithm more
robust when handling datasets with considerable outliers. Moreover, given that
most binarized data has no ordinality, a calculated ”mean” would not provide
any meaningful insights.
The algorithm first takes the N datapoints from the Binary Maximum Dispersion
stage. These become the initial medoids. All non-medoid datapoints are then
assigned to their nearest medoid based on hamming distance to form N clusters.
Next, the cumulative distance from each datapoint is calculated to all other
datapoints within the same cluster. The datapoint in each cluster with the
smallest cumulative distance is then selected to be the new medoid for that
cluster. All datapoints are then assigned to their nearest medoid and the
process is iterated. The algorithm converges when the medoids are unchanged
between iteration cycles.
A visualisation of the final result of this process may be seen in Figure 7.

Figure 5: Pre-Sort Architecture Figure 6: Binary Maximum Dispersion Figure 7:
Binary K-Medoid Clustering

###  3.3 Genetic Class Alignment

The dataset now consists of N clusters within each class. Given that the
Tsetlin Machine functions by mining frequent sub-patterns and using these to
differentiate between the classes, the optimal strategy is to align clusters
based on maximal inter-class hamming distance and to distribute these to N
separate Tsetlin Machines.
To illustrate this concept, Figure 8 shows 4 final medoids from the previous
stage for a handwritten digit dataset. Two are from Class ”1” and two are from
Class ”7”. Medoid A shows a classic number 1 with a vertical stroke whereas
Medoid B shows an italicised style 1 with a rightward slanting stroke. Medoid
C shows a 7 with a vertical line and leftward stroke, whereas Medoid D shows a
more classic rightward slanting stroke and leftward stroke. The ”+” symbol
indicates that no marking was detected for this bit in the datapoint. The ”0”
symbol indicates a marking was detected for this bit and this marking location
is shared with the medoid vertically aligned with it. The ”1” symbol indicates
a marking was detected for this bit and this marking location is not shared
with the medoid vertically aligned with it. Using these symbols to aid us, it
is clear that there are only 3 bits different (hamming distance) between
Medoid A and Medoid C and 4 bits different between Medoid B and Medoid D. In
fact, Medoid A is wholly encompassed within Medoid C and Medoid B is wholly
encompassed within Medoid D. This makes classification by sub-pattern
identification relatively difficult between these medoids.
Figure 8 shows a different alignment with Medoids C and D switched. The
hamming distances between the vertically aligned medoids have now
significantly increased. This leads to more unique sub-patterns that can be
learned to differentiate between Medoids A and D and Medoids B and C, making
the task of the Testlin Machine easier. To implement this concept, the final
medoids from the K-Medoid stage (N medoids within each class) are placed with
their class peers into 1D horizontal arrays. These arrays are then vertically
stacked as shown in Figures 8 and 9 (such that each row represents one class).
The total cumulative hamming distance between each medoid in a vertical stack
is calculated and then summed for all vertical stacks to give a total hamming
distance for the 2D configuration. An expedited genetic algorithm is used to
search for the 2D configuration with the largest total hamming distance. The
columns (containing one cluster from each class) are then used to separate the
dataset in N smaller datasets. These are then processed by their own
independent Tsetlin Machine.

Figure 8: Pre-Alignment Class Medoids Figure 9: Post-Alignment Class Medoids

##  4 Experiments

The pre-sort architecture was written in C++ to match the Tsetlin Machine code
provided on the main CAIR (Centre for Artificial Intelligence Research)
repository [3]. Four MNIST style datasets were chosen for classification. The
original MNIST dataset, containing handwritten digits from 0 to 9, EMNIST, the
Extended MNIST dataset, KMNIST, the Kuzushiji MNIST datatset consisting of
handwritten Japanese characters (contains class-overlap, multiple characters
per class) and FMNIST, the Fashion MNIST dataset consisting of 28x28 graphical
representations of common clothing items. These datasets were binarized using
a simple thresholding method [4] (($<X$ set to 0), ($>=X$ set to 1)).
Datasets were classified with a varying number of medoids (2,4,8,16,32). Two
runtime strategies were chosen. The first consisted of running both the
baseline Tsetlin Machine algorithm and proposed pre-sort method for 100
epochs, then running inference. This determined the training time, inference
time and accuracy. However, as the number of medoids was increased during the
experiment, it became apparent that some pre-sort Tsetlin Machines reached
100% accuracy within 4-6 epochs, after which, it was superfluous to continue
training. The second strategy was therefore to run an inference between each
training cycle for these pre-sort Tsetlin Machines. When 100% accuracy was
reached, the training was concluded. The training runtime for this method
includes the inference time required to check the accuracy after each training
epoch. The results presented show the fastest of these two methods for the
pre-sort training time, as both are legitimate training strategies. All
dataset/medoid points were performed 10 times using unique 80/20 train/test
splits of the datasets and the average (mean) is presented. 4000 clauses per
class were used for the baseline Testlin Machine implementation as suggested
on the CAIR repository. For the pre-sorted Tsetlin Machines, 4000 clauses per
class were used in total across all distributed Tsetlin Machines (eg N=2,
$\mathtt{\sim}$2000 clauses per class per machine). As the clustering is non-
uniform, the number of clauses assigned to each distributed Tsetlin Machine
was apportioned based on the total number of datapoints assigned to that
Tsetlin Machine. Other options are available, but were not explored. All runs
were performed single-threaded on a first-gen M1 Macbook Pro.

##  5 Results

Figure 10 shows the classification test accuracy between the baseline Tsetlin
Machine algorithm through varying medoid configurations for the four chosen
datasets. Critical datapoints for the test accuracy can be found in Table 1.
Figure 11 shows the training time between the baseline Tsetlin Machine
algorithm through varying medoid configurations for the four chosen datasets.
Critical datapoints for the training time can be found in Table 2.
Figure 12 shows the inference time between the baseline Tsetlin Machine
algorithm through varying medoid configurations for the four chosen datasets.
Critical datapoints for the inference time can be found in Table 3.

TABLE I: Accuracy | FMNIST | KMNIST | EMNIST | MNIST
---|---|---|---|---
Baseline | 89.50% | 96.07% | 98.45% | 97.88%
Pre-Sorted | 99.81% | 99.50% | 99.86% | 99.86%
Gain | 10.32% | 3.43% | 1.41% | 1.98%
TABLE II: Training Time | FMNIST | KMNIST | EMNIST | MNIST
---|---|---|---|---
Baseline | 4484 s | 4336 s | 2424 s | 3472 s
Pre-Sorted | 11.72 s | 30.89 s | 15.58 s | 15.58 s
Speed Up | 382.5X | 140.4X | 155.6X | 222.9X
TABLE III: Inference Time | FMNIST | KMNIST | EMNIST | MNIST
---|---|---|---|---
Baseline | 36.6 s | 34.3 s | 20.0 s | 31.4 s
Pre-Sorted | 0.43 s | 0.43 s | 0.32 s | 0.32 s
Speed Up | 85.8X | 79.7X | 62.9X | 98.8X
Figure 10: Accuracy Figure 11: Training Time Figure 12: Inference Time

##  6 Discussion

It can be seen from Figure 10 that for all datasets, the test accuracy
improves for the pre-sorted Tsetlin Machine when compared to the baseline
implementation (in some instances, markedly so). There are several reasons for
this. One reason is class-overlap (more than one ”symbol” or ”character” per
class). The results demonstrate that the baseline Testlin Machine has
difficulty with this concept as it mines frequent sub-patterns during training
to form the clauses. With class-overlap, the sub-patterns are different for
each unique symbol and the feedback mechanism can alter clauses from one
”symbol” with feedback from another ”symbol” within the same class. In pre-
sorted Tsetlin Machine, dissimilar ”symbols” are separated and farmed out to
independent smaller Tsetlin Machines, so this situation is inherently handled.
Another issue is translation (identical patterns occurring in differing
locations between datapoints). In the baseline Tsetlin Machine, different sub-
patterns have to be learned for each location that a sub-pattern appears in. A
sliding window mechanism has been tested to solve this issue with baseline
Tsetlin Machine [5], however, this adds considerable complexity and
dramatically increases the training and inference times. In pre-sorted Tsetlin
Machine, this is inherently handled as the different translations are simply
sorted into separate clusters and processed in independent Tsetlin Machines.
It can be seen from Figure 11 that for all datasets, the training time is
drastically reduced for the pre-sorted Tsetlin Machine with respect to the
baseline implementation. There are several reasons for this. Principally,
fewer clauses are run per training cycle. This is because in the baseline
Tsetlin Machine, 4000 clauses are updated for every datapoint passed into a
class. In pre-sorted Tsetlin Machine, only 1/N * 4000 clauses are updated on
average per datapoint. This immediately results in a training runtime
reduction by a factor of N. Another reason is that having pre-simplified the
problem, the test accuracy reached 100% for some pre-sorted Tsetlin Machines
after only a few epochs. It was therefore faster to adopt a strategy of
testing for this condition and then terminating training rather than running
for an extensive period of time.
It can be seen from Figure 12 that for all datasets, the inference time is
drastically reduced for the pre-sorted Tsetlin Machine with respect to the
baseline implementation. The reason for this is identical to the reduction in
training time. The number of clauses required for an inference is reduced by a
factor of N, lowering the computational complexity and therefore reducing the
runtime.
As the entire pre-sort architecture may be parallelised, a further
train/inference run time reduction of at least a factor of N is achievable
against the results herein presented.

###  6.1 Momentary Mastery

As the original Tsetlin Machine is split out into smaller independent Tsetlin
Machines in the proposed pre-sort scheme, a unique opportunity is presented
for problems that only require ”one-shot” training and inference (eg training
is performed, inference is performed, the results are stored and the model
deleted). As each datapoint only requires one smaller independent Tsetlin
Machine for training and inference and the datapoints are grouped together,
only one of the smaller independent Tsetlin Machines needs to exist at any
given time. This would result in a memory footprint reduction by a factor of
N, provided that a single threaded training/inference speed was acceptable.
This is a considerable saving for embedded/edge devices.

###  6.2 Hardware Impact

The heart of the Tsetlin Machine algorithm is really three simple
instructions: AND, XNOR and popcount. The AND and XNOR operations are used to
quickly match set/unset bits between the clauses and the datapoint whilst
calculating the clause outputs. Popcount is used to quickly count set bits in
words corresponding to clause votes during training and inference. Optimising
hardware for these instructions can improve the performance of the algorithm.
Whilst Section 3 provided sound conceptual reasoning behind why each of the
three stages of the pre-sort architecture were chosen, perhaps more
importantly, there is synergy with the hardware requirements of Tsetlin
Machine. The heart of all three pre-sort stages is the hamming distance
calculation: XOR followed by popcount. Whilst AND, XOR and XNOR (bitwise
equality) are common logical operators, popcount is typically omitted in RISC
architectures. Hence, extending these architectures with the additional
popcount instruction improves the entire proposed pre-sort architecture, not
just the Tsetlin Machine.

##  7 Final Comments

This work proposed and investigated a pre-sort architecture for Tsetlin
Machines. Results were presented that demonstrated up to 10% improvement in
accuracy, $\mathtt{\sim}$383X reduction in training time and
$\mathtt{\sim}$86X reduction in inference time. A full delineation of how this
was achieved was discussed, along with methods to reduce memory footprint and
hardware considerations for improving performance.

## References

  * [1] Ole-Christoffer Granmo.  The tsetlin machine - A game theoretic bandit driven approach to optimal pattern recognition with propositional logic.  CoRR, abs/1804.01508, 2018.
  * [2] Ashur Rafiev.  Visualization of machine learning dynamics in tsetlin machines.  In 2022 ISTM, 2022.
  * [3] Ole-Christoffer Granmo.  Centre for artificial intelligence research, 2018.  https://github.com/cair/TsetlinMachine.
  * [4] K. Abeyrathna.  Adaptive continuous feature binarization for tsetlin machines applied to forecasting dengue incidences in the philippines.  In 2020 IEEE SSCI, pages 2084–2092, 2020.
  * [5] Ole-Christoffer Granmo.  The convolutional tsetlin machine.  CoRR, abs/1905.09688, 2019.

|  Jordan Morris (MEng ‘13, PhD ‘18 – Newcastle University, UK) was previously
a research fellow at Arm as part of the Applied Silicon research group. He
most recently worked at Mignon AI focusing on software and ASIC design of low
power, bitwise AI algorithms. His research interests include novel symbolic AI
architectures, massively parallel architectures and custom hardware design
(FPGA/ASIC).
---|---