# Structural Similarity: When to Use Deep Generative Models on Imbalanced
Image Dataset Augmentation

Chenqi Guo1 Fabian Benitez-Quiroz1 Qianli Feng1,2 Aleix Martinez1,2
1The Ohio State University 2Amazon
{guo.1648, benitez-quiroz.1, feng.559<EMAIL_ADDRESS>
###### Abstract

Improving the performance on an imbalanced training set is one of the main
challenges in nowadays Machine Learning. One way to augment and thus re-
balance the image dataset is through existing deep generative models, like
class-conditional Generative Adversarial Networks (cGAN) or Diffusion Models
by synthesizing images on each of the tail-class. Our experiments on
imbalanced image dataset classification show that, the validation accuracy
improvement with such re-balancing method is related to the image similarity
between different classes. Thus, to quantify this image dataset class
similarity, we propose a measurement called Super-Sub Class Structural
Similarity (SSIM-supSubCls) based on Structural Similarity (SSIM). A deep
generative model data augmentation classification (GM-augCls) pipeline is also
provided to verify this metric correlates with the accuracy enhancement. We
further quantify the relationship between them, discovering that the accuracy
improvement decays exponentially with respect to SSIM-supSubCls values.

##  1 Introduction

Figure 1: An example of data augmentation application with our proposed deep
generative model data augmentation classification (GM-augCls) pipeline on
iNaturalist-2019 Fungi dataset. (Top) exampled original and synthesized images
for visualization. (Bottom) bar plot of the image number in each class for the
original and synthesized dataset. After the augmentation procedure, the new
dataset becomes balanced. In this paper, a class similarity metric for image
dataset, called Super-Sub Class Structural Similarity (SSIM-supSubCls) is
constructed for measuring the image similarity between different classes. We
further quantify the relationship between this metric value and the
classification accuracy improvement after GM-augCls procedure, discovering
that the accuracy improvement decays exponentially with respect to SSIM-
supSubCls values.

Machine learning with imbalanced dataset is still a challenging and open task.
Many efforts have been made to mitigate the bias towards the majority classes
and thus enhance the generalization of classifiers trained on such image
datasets. Common strategies concerning adding weights for each class in the
loss function [8], re-balancing the dataset by over-sampling the minority
classes or under-sampling the majority classes [5] are widely used. As one of
the most popular over-sampling techniques, geometric transformations like
rotations or mirroring may interfere with orientation-related features in the
image. SMOTE [6] can be used to solve the over-sampling problem by creating
synthetic data based on the nearest neighbors of a sample in an embedding or
image space. Other techniques attempt to use images from the web [19],
knowledge transfer [7] and GAN architectures generating artificial images [11,
20, 4, 21] to enlarge the minority classes. For image related tasks, one way
to augment the dataset is through deep generative models, like class-
conditional Generative Adversarial Networks (cGAN) or Diffusion Models, by
synthesizing artificial images on the tail-classes to make the training set
balanced.

However, some classification tasks are inherently harder than others,
especially in the absence of data. For instance, intuitively the
classification task in Figure 1 is easier than Figure 2: the two classes in
Figure 2 share similar background, object shape and color, and the distinction
between these two bird species requires subject matter expertise. In this
case, deep generative models would produce unfaithful reconstructions, since
small but important differences between class object attributes are inherently
difficult to be generated. Therefore, the downstream classification
performance may not be improved and in some scenarios even negatively
impacted. Hence the question comes naturally when we can use deep generative
model data augmentation to refine classification performance.

Figure 2: An example of iNaturalist-2019 Birds dataset with high image
similarity between classes. Here class 202 and class 203 share similar
background, bird shape and color. Hence, expert specialities are required to
distinguish between these two species.

In our work, we propose a metric measuring the dataset image similarity
between different classes based on Structural Similarity (SSIM), called Super-
Sub Class Structural Similarity (SSIM-supSubCls). For such metric, higher
value suggests higher class similarity. Furthermore, we provide a pipeline
named deep generative model data augmentation classification (GM-augCls),
which uses StyleGAN2 based cGAN [22] or guided-diffusion model [10] to
generate images. The synthesized images are then passed through a classifier
trained on the original dataset to calculate the likelihood of each new image
being part of the target class. Only images with a high likelihood are
appended to the training set. Experiments reveal that the accuracy improvement
decays exponentially with respect to the metric values. The whole idea is
shown in image Figure 1.

We summarize our contributions as follows:

  * •

We propose a metric measuring image dataset class similarity (section 3.3
SSIM-supSubCls). A lower metric value implies lower image similarity across
different classes.

  * •

We propose a data augmentation pipeline re-balancing the imbalanced image
dataset using existing deep generative models, like cGAN or diffusion models,
jointly with a classifier as image filtering technique.

  * •

We evaluate our proposed metric and pipeline on imbalanced dataset, including
iNaturalist-2019 [24], flowers [1], UTKFace [3] and scene [2] dataset.
Qualitative and quantitative results suggest that the pipeline can faithfully
generate high quality images. Experiments also show that the top1 validation
accuracy increment after dataset re-balancing decays exponentially with
respect to the metric values. With this exponential curve fitted, one can
easily predict the expected accuracy improvement for any image dataset from
its SSIM-supSubCls value.

##  2 Related Works

###  2.1 Imbalanced Dataset

Many real-world datasets are not uniformly distributed over different classes.
Such imbalanced datasets bring in biases towards the majority classes and
affect the generalizability of classifiers trained on them. Widely used
solutions include imposing inductive bias, or statistical re-sampling or re-
weighting to alleviate the extreme imbalance. To enhance the learning
performance of imbalanced data, [17] sought a principled approach to select
unlabeled data in the wild scaling up the original dataset using contrastive
learning approach. Showing that real world dataset often has a long-tailed and
open-ended distribution, [19] defined Open Long-Tailed Recognition (OLTR) as
learning from such naturally distributed data and optimized the classification
accuracy by handling tail recognition robustness with dynamic meta-embedding
over a balanced test set. To deal with the shift in the testing label
distribution caused by training set imbalance, [23] derived a post-training
prior re-balancing technique through a KL-divergence based optimization.

###  2.2 Data Augmentation and Deep Generative Models

When the training image dataset is imbalanced, the classification accuracy can
be significantly deteriorated, especially for the tail classes. One way to
mitigate this problem is through data augmentation on minority classes.
Traditional methods include geometric transformation like image rotations or
translations, re-sampling with SMOTE [6] or ADASYN [13]. Efforts have also
been made to use deep generative models, like class-conditional GAN (cGAN)
[22] or diffusion models [10] to restore the dataset balance by synthesizing
minority-class samples.

[11] experimented with different GAN architectures generating new training
data for classification tasks and showed that the GAN improved the results
compared with the original imbalanced dataset. [20] proposed a balancing
generative adversarial network (BAGAN) architecture to generate new images for
minority-class. [4] used a Data Augmentation Generative Adversarial Network
(DAGAN) for data augmentation by taking data from a source domain and
generalising it to a different low-data target domain. Class-conditional GAN
(cGAN) extends the standard unconditional GAN to learning data-label
distributions and hence capable of generating images belonging to specific
classes. Observing that class-conditioning causes mode collapse in limited
data settings, where unconditional learning leads to satisfactory generative
ability, [22] suggested a transitional training strategy for cGANs that
effectively prevents mode-collapse by leveraging unconditional learning. This
strategy starts with an unconditional GAN and gradually injects conditional
information into the generator and the objective function.

Diffusion model is a parameterized Markov chain trained with variational
inference to produce samples matching the data after finite steps [16].
Transitions of this chain are learned to reverse a diffusion process, which is
a Markov chain that gradually adds noise to the data in the opposite direction
of sampling until the signal is destroyed. Showing that diffusion models can
achieve image sample quality superior to the current state-of-the-art GANs,
[10] improved the synthesized image quality with a classifier guidance.

In our proposed data augmentation pipeline, both cGAN with transitional
training strategy [22] and the guided-diffusion model [10] are adopted and
experimented.

##  3 Method

In this section, we are going to talk about why we choose SSIM as the basis of
our proposed metric in Section 3.1, how we group the dataset sub-classes
(i.e., the original classes) into super-classes to compute the metric value in
Section 3.2, how the metric is constructed in Section 3.3, and how we are
going to augment the imbalanced image dataset using our proposed pipeline in
Section 3.4.

###  3.1 Structural Similarity

As introduced in [26], human visual system is able to assess the perceptual
similarity between two images and highly sensitive to structural differences.
To measure images differences, naive metrics such as mean squared error (MSE)
and peak signal-to-noise ratio (PSNR) cannot capture the perceived visual
quality. Hence as an alternative, Structural Similarity Index (SSIM) [25]
seeks to compare the structures of the reference and the distorted image
signals, which indeed correlates more with human cognitive understanding.

The SSIM compares the local patterns of pixel intensities in images that the
luminance and contrast have been normalized. It separates the task of
similarity measurement into three comparisons: luminance, constrast and
structure. Suppose $\boldsymbol{x}$ and $\boldsymbol{y}$ are two images
aligned with each other. Denote the mean intensity as $\mu_{x}$ and $\mu_{y}$,
the standard deviation as $\sigma_{x}$ and $\sigma_{y}$, and the covariance as
$\sigma_{xy}$. Choose the constant $C_{1}=(K_{1}L)^{2}$ where $L$ is the
dynamic range of the pixel values (255 for 8-bit grayscale images), and
$K_{1}\ll 1$ is a small constant. Similarly, choose constant
$C_{2}=(K_{2}L)^{2}$, and $K_{2}\ll 1$. Then these three components can be
combined to yield a final image similarity measurement:

$\mathrm{SSIM}(\boldsymbol{x},\boldsymbol{y})=\frac{(2\mu_{x}\mu_{y}+C_{1})(2\sigma_{xy}+C_{2})}{(\mu_{x}^{2}+\mu_{y}^{2}+C_{1})(\sigma_{x}^{2}+\sigma_{y}^{2}+C_{2})}$
(1)

The SSIM metric returns one when the two images $\boldsymbol{x}$ and
$\boldsymbol{y}$ are identical and decreases as differences become more
relevant. A value of zero indicates no structural similarity. In this paper,
we extend the concept of structural similarity to image dataset classes
hierarchy as shown in Section 3.2.

###  3.2 Super-class Information for Image Dataset

Real world datasets usually follow long-tail instead of uniform class
distributions. Figure 3 shows the class distribution of iNaturalist-2019 Birds
[12] as an example of such imbalanced dataset.

Figure 3: (Top) Sample images of the original iNaturalist-2019 Birds dataset
from different super-classes (here only 4 of 9 super-classes are presented for
visualization). Though images are from different sub-classes, within each
super-class they share similar bird attributes and thus are grouped together.
(Bottom) Bar plot for its class distribution. Notice that the distribution of
the original dataset is imbalanced and the one after GM-augCls is balanced.

A naive image dataset similarity measurement would be directly computing the
average of SSIM values of every image versus the other images in the dataset.
Unfortunately, this will be computationally expensive for large scale
datasets. Thus, we seek to alleviate the time complexity by bootstrapping.
Basically, what we want to calculate is an expectation of the SSIM within an
image set, as in Eq. 2. In practice, each time we can randomly pick a pair of
images $\mathbf{I}_{i}\neq\mathbf{I}_{j}$ from the set $\mathcal{X}$ and
evaluate their SSIM. This procedure should be repeated enough times (here we
use $2\times$ number of images in the whole imbalanced dataset) until the
average of SSIM values converge, and the final similarity measurement would be
the mean of the SSIM values on each pair of images.

$\mathrm{SSIM_{set}}(\mathcal{X})=\mathbb{E}[\underset{\mathbf{I}_{i},\mathbf{I}_{j}\in_{R}\mathcal{X}}{\mathrm{SSIM}}(\mathbf{I}_{i},\mathbf{I}_{j})]$
(2)

If we simply set $\mathcal{X}$ consisting all the images in the whole
imbalanced training set, we can get a straightforward metric, called Merged-
Class Structural Similarity (SSIM-mergeCls). However, through mixing up images
from all classes, we are in the risk of losing important information of the
original dataset class structure. Thus, instead of using the flat structure
(all classes at same level) for a classification task, we use a hierarchical
class structure based on some ontology or human annotations.

One may notice that many existing image datasets for classification tasks can
be further grouped into broader classes (i.e., super-classes) which subsume
several of the original classes (i.e., sub-classes) that keep same image
attributes under specific metrics [27]. This super-class information can be
used in this scenario. For a natural world creatures dataset like
iNaturalist-2019 Birds in Figure 3, these super-classes are formed through
human inspections in a top-down manner, as in Figure 4:

  1. 1.

First, all the sub-classes in the original dataset are grouped according to
their species. E.g., in Birds dataset, super-class 1 (Oriole), super-class 2
(Crow), super-class 3 (Sparrow), super-class 4 (Seagull) and super-class 5
(Eagle) are grouped in this step.

  2. 2.

Then, based on the image background, the sub-classes difficult to be clustered
in step 1 are further grouped by their habitats. E.g., forest bird super-class
6 and super-class 7 versus aquatic bird super-class 8 and super-class 9.

  3. 3.

Finally, based on the object details, super-classes acquired in step 2 can be
further grouped by the bird size, shape and color. E.g., large aquatic bird
super-class 8 v.s. small aquatic bird super-class 9.

Figure 4: The resulting class hierarchy of iNaturalist-Birds dataset by grouping the original sub-classes. The whole dataset contains 9 super-classes and each super-class consists of various sub-classes. Dataset | UTKFace | Birds | Insects | scene | flowers | Fungi | Reptiles | Amphibians
---|---|---|---|---|---|---|---|---
sup-cls 1 | 5 | 9 | 14 | 6 | 5 | 4 | 2 | 4
sub-cls 2 | 5 | 126 | 141 | 6 | 5 | 12 | 39 | 10
1 The number of super-classes in the dataset
2 The number of sub-classes (i.e., original classes) in the dataset
Table 1: The number of classes in each dataset.

Table 1 provides the number of classes in each dataset we used in this study.
Note that for dataset UTKFace, scene and flowers, each super-class only
contains one sub-class since the original datasets are already grouped by
species. The grouping law for other datasets are provided in Supplemental
Material Section S2. With these super-class information, we propose a metric
taking a narrower scope of image classes into consideration, called Super-Sub
Class Structural Similarity (SSIM-supSubCls). Therefore, a more relevant class
similarity measurement is acquired.

###  3.3 SSIM-supSubCls Metric

In our proposed SSIM-supSubCls metric, rather than calculating the SSIM from
the whole training set $\mathcal{X}$, we compute it from the super-class set
$\mathcal{X}_{k}$, as in Eq. 3. Practically, each time we randomly select a
pair of images $\mathbf{I}_{a}\neq\mathbf{I}_{b}$ from the super-class set
$\mathcal{X}_{k}$ and evaluate their SSIM. This process is also repeated
enough times (here we use $2\times$ number of images in each super-class set
$\mathcal{X}_{k}$) until the average of SSIM values converge. The similarity
measurement on each super-class $k$ would be the mean of the SSIM values on
each pair of images in $\mathcal{X}_{k}$.

Considering the fact that for classification, the classes most difficult to be
distinguished are the key impact factors on performance. Thus, our final SSIM-
supSubCls measurement would be the maximum of the SSIM values on every super-
class set $\mathcal{X}_{k}$, which indicates the largest similarity among all
super-classes.

$\mathrm{SSIM_{supSubCls}}(\mathcal{X})=\underset{\mathcal{X}_{k}\subset\mathcal{X}}{\max}\\{\mathrm{SSIM_{set}}(\mathcal{X}_{k})\\}$
(3)

This metric provides a prior knowledge on whether the deep generative model
data augmentation works on the image data classification by measuring its
image similarity within super-class set. Considering that deep generative
models like cGAN or diffusion model can faithful generate images from
different classes which embrace large distinctions like species, but struggle
on reconstructing the very subtle distinctions on the image objects, e.g., if
there exists black feathers on the birds’ wings or not (as in Figure 3 (Top)
super-class 4 Seagulls). it is not the case that deep generative model data
augmentation can improve classification performance on every dataset.
Therefore, our proposed metric will give the researcher insights on which data
augmentation method should use instead of blindly apply the GM-augCls on any
image datasets. From the definition in Eq. 3, higher SSIM-supSubCls value
indicates higher similarity among super-classes in the dataset, harder for the
deep generative model to reconstruct the details in the images for
distinguishing between sub-classes within this super-class, and thus a less
chance to get benefits from the GM-augCls.

###  3.4 cGAN-aug Classification Pipeline

Figure 5: The schematic diagram of our proposed Deep Generative Model Data
Augmentation Classification (GM-augCls) method. First, a deep generative model
(GM) $M$ and a classifier $C(\cdot)$ are trained on the whole imbalanced
training set $\mathcal{X}$. $M$ is trained only once, while $C(\cdot)$ gets
updated each time by training on the new dataset $\mathcal{X}^{\prime}$
augmented with qualified new images. This whole procedure is iterated several
steps, and in every step $C(\cdot)$ is replaced with $C^{\prime}(\cdot)$
acquired in the immediate previous step. The augmented
$\mathcal{X}^{\prime\prime}$ is the final balanced dataset we want.

In this section we propose a pipeline to verify that our metric correlates
with the deep generative model data augmentation method for improving
classification performance. An illustrative figure of the pipeline called GM-
augCls is provided in Figure 5. This figure shows that, in an iterative way,
using existing deep generative models like cGAN or diffusion model and
classifiers, we can generate a new balanced dataset augmented by qualified
artificial images. By qualify, we mean, that only synthesized images with
large probability during the classification steps are kept to enlarge the
dataset.

In practice, we use a StyleGAN2 [18] based cGAN with transitional training
strategy [22] or guided-diffusion model [10] to generate artificial images as
potential ones to augment the imbalanced dataset. These deep generative models
are trained on the original imbalanced training set. Then a ResNet [15] or
Masked Autoencoder (MAE) [14] classifier also trained on the original set with
sub-class labels are applied on the synthesized images to select qualified
ones. The selected images combined with the original ones compose our final
balanced dataset.

Our goal is to enhance the classification performance on an imbalanced image
dataset. The deep generative model can generate images belonging to each sub-
class under the user’s control of synthesized image numbers. However, not all
new images fall in a desired sub-class, even with cGAN capable of generating
images belonging to specific classes, as the deep generative model is trained
with the whole dataset. Thus, we need a classifier to pick images only in the
expected class. As shown in Fig 5 step 1, since at the beginning no artificial
images have been used to augment the dataset, we use a classifier $C(\cdot)$
trained on the whole original imbalanced set $\mathcal{X}$ to classify each
sub-class. Under a prediction probability threshold $\alpha$, $C(\cdot)$
select from all the synthesized images to get qualified ones as new members of
the augmented balanced set $\mathcal{X}^{\prime}$. This means that the to-be-
balanced dataset and the to-be-improved classifier are combat with each other:
on one hand we use the dataset to train the classifier, on the other hand we
use the classifier to boost the dataset.

Thus, the above mentioned process is iterated several steps. In each step the
pretrained classifier $C(\cdot)$ is replaced with the $C^{\prime}(\cdot)$ one
trained on the new set $\mathcal{X}^{\prime}$ acquired in the immediate
previous step, until the validation accuracy with $C^{\prime}(\cdot)$ is not
improved under a specific tolerance $\epsilon$. In practice, this is repeated
for at most two steps in our experiments. Finally, the augmented set
$\mathcal{X}^{\prime\prime}$ is the balanced dataset we want.

###  3.5 Selection on Classifier and Deep Generative Model

In our work, the classifier used to select qualified images and validate the
classification accuracy is ResNet18 [15]. To justify our proposed metric and
pipeline work regardless of the classifier selection, we also provide the
results with Masked Autoencoder (MAE) ViT-H128 [14] which shows state-of-the-
art results in dataset such as [12].

For the GAN architecture, we use StyleGAN2 [18] based cGAN on the original
imbalanced image dataset. Observed that class-conditional learning leads to
mode collapse while the unconditional one still maintains satisfactory
generative ability under limited data settings, [22] proposed a learning
approach which starts with an unconditional GAN and gradually injects class
conditional information into the generator and the objective functions. Our
pipeline with cGAN adopts this transitional training strategy.

Diffusion models, which can achieve image sample quality superior to the
current state-of-the-art GANs, is also experimented in our pipeline.
Specifically, guided-diffusion [10] improving the synthesized image quality
with a classifier guidance is used.

##  4 Experiments

###  4.1 Experimental Settings

To evaluate the above proposed methods, we carried out our major experiments
on dataset iNaturalist-2019 [12], flowers [1], UTKFace [3] and scene [2] which
are either long-tail or imbalanced distributed. The iNaturalist-2019 has
around 265K images in the long-tail training set and 3k images in a balanced
validation set with 6 categories, and each category contains different number
of sub-classes. Here we are using the categories of Insects, Birds,
Amphibians, Fungi and Reptiles for experiments. The flowers dataset contains
nearly 4k images in the imbalanced training dataset with 5 sub-classes. The
UTKFace dataset is a large-scale human face dataset with 5 different ethnicity
across long age span. In this work we are predicting their ethnicity. The
imbalanced scene dataset contains about 25k images from a wide range of
natural scenes with 6 different sub-classes. Class number distributions of all
these datasets are shown in Supplemental Material Section S3.

In our experiments, the deep generative models, ResNet18 and MAE classifiers
are first trained on the original imbalanced set with sub-class instead of
super-class labels. cGAN models are trained until the Frechet Inception
Distance (FID) scores converge. The diffusion models are trained for 100k
iterations resumed on an ImageNet [9] pretrained model. To guide the diffusion
model during sampling, an additional classifier is also trained until its
validation accuracy converges [10]. The ResNet18 classifiers are trained for
100 epochs and the MAE for 50 epochs when their validation accuracy converges,
with their hyper-parameters remaining the same throughout the whole procedure
in each case.

In this paper, we only report the classification results at the final step.
The maximum top1 validation accuracy are provided before and after the GM-
augCls pipeline. To verify if the SSIM-subSupCls correlates with the
classification accuracy improvement, the metric values are measured on the
original imbalanced training sets.

###  4.2 Qualitative Evaluation Results

Table 2 provides the FID scores for the StyleGAN2 based cGAN and GD models.
Figure 6 also provides sample images as a comparison between the original and
GM-augCls synthesized ones. They demonstrate our data augmentation method can
generate high quality images for each sub-class after classifier selection.

Dataset | StyleGAN2 FID | GD FID
---|---|---
UTKFace | 4.37 | -
Birds | 4.68 | 28.25
Insects | 6.56 | -
scene | 9.84 | 54.34
flowers | 15.21 | -
Fungi | 8.67 | 50.08
Reptiles | 6.60 | -
Amphibians | 11.74 | -
Table 2: FID scores for StyleGAN2 based cGAN and Guided Diffusion on each
dataset. Figure 6: Results for qualitative evaluation of our proposed GM-
augCls pipeline. These sample images indicate that our pipeline can synthesize
high quality images belonging to each sub-class even though the deep
generative models are trained on the whole original dataset. More sample
images are provided in Supplemental Material Section S4.

###  4.3 Quantitative Evaluation Results

We tested our metric and pipeline on dataset iNaturalist-2019, flowers,
UTKFace and scene with the original balanced validation set. Table 3 shows
their top1 validation accuracy with cGAN and guided-diffusion (GD) models
trained on the original and cGAN-augCls or GD-augCls augmented dataset. For
ablation study, results on the cGAN augmented datasets without image selection
are also provided as baseline.

As in Table 3, for dataset flowers, iNaturalist-2019 Fungi, Reptiles and
Amphibians, compared with the ResNet18 classifier trained on the original
imbalanced set, the ones trained on the cGAN-augCls balanced set have
significantly enhanced accuracy. To certify that this conclusion can be drawn
regardless of the classifier selection, we also conduct the experiments with
MAE classifier and the same results are obtained. Supplemental Material
Section S5 also provides learning curves during this procedure.

Dataset | Original Acc | cGAN-aug Acc 1 | cGAN-augCls Acc | GD-augCls Acc
---|---|---|---|---
ResNet18 | MAE | ResNet18 | MAE | ResNet18 | MAE | ResNet18
UTKFace | 82.31% | 87.63% | 83.32% | 86.62% | 84.29% | 86.82% | -
Birds | 52.12% | 80.42% | 52.12% | 80.16% | 54.50% | 80.16% | 55.03%
Insects | 61.23% | 87.23% | 59.34% | 86.29% | 61.70% | 87.23% | -
scene | 90.12% | 94.29% | 90.53% | 94.35% | 90.65% | 94.41% | 90.24%
flowers | 64.14% | 95.40% | 79.86% | 95.86% | 80.00% | 96.55% | -
Fungi | 50.00% | 88.89% | 66.67% | 88.89% | 75.00% | 88.89% | 69.44%
Reptiles | 28.21% | 81.20% | 38.63% | 79.49% | 41.03% | 82.05% | -
Amphibians | 20.00% | 74.67% | 43.33% | 76.67% | 36.67% | 80.00% | -
1 When trained on cGAN augmented balanced dataset without classifier selctions (as baseline) |
Table 3: Quantitative results of our proposed pipeline with ResNet18 and
Masked Autoencoder (MAE) for image selection and evaluation. Here we list the
maximum top1 classification validation accuracy within 100 epochs for ResNet18
and 50 epochs for MAE. All classifiers are trained on the original imbalanced
set and the balanced set after data augmentation pipeline respectively.

As a well-known regularization-based method, class-balanced loss (CB-loss) [8]
is specifically designed to add weights for each class in the loss function.
For comparison, Table 4 also provides the top1 validation accuracy training
with ResNet18 CB-loss on the original dataset. Compared with the results in
Table 3, using Effective Number Class Balanced loss does not improve the
accuracy as much as our proposed pipeline.

Dataset | UTKFace | scene | flowers | Amphibians
---|---|---|---|---
CB-loss Acc | 73.65% | 87.71% | 75.86% | 20.00%
Table 4: Top1 validation accuracy with ResNet18 CB-loss training on the
original dataset.

To verify that our proposed metric correlates with the accuracy improvement,
we measure the SSIM-mergeCls and SSIM-supSubCls values for each dataset. Table
5 summarises their metric values. This table shows that the deep generative
model data augmentation method only works when the metric values are small.
This observation confirms our hypothesis that for an image dataset with high
similarity between classes, the deep generative model suffers in unfaithfully
reconstructing the subtle distinctions between class features and the
classifiers struggles on distinguishing various classes, which leads to a
lower classification accuracy improvement.

Dataset | SSIM-mergeCls | SSIM-supSubCls | cGAN-augCls Acc Impr 1 | cGAN-augCls Works
---|---|---|---|---
UTKFace | 0.3649 | 0.3834 | 2.41% | $\times$
Birds | 0.1698 | 0.3742 | 4.57% | $\times$
Insects | 0.1373 | 0.3115 | 0.77% | $\times$
scene | 0.1462 | 0.2625 | 0.59% | $\times$
flowers | 0.1319 | 0.1652 | 24.73% | $\checkmark$
Fungi | 0.0617 | 0.0880 | 50.00% | $\checkmark$
Reptiles | 0.0645 | 0.0793 | 45.44% | $\checkmark$
Amphibians | 0.0725 | 0.0792 | 83.35% | $\checkmark$
1 The relative accuracy improvement on cGAN-augCls Acc with ResNet18
classifier (calculated from Table 3 normalized by the original accuracy)
Table 5: This table provides the SSIM-mergeCls and SSIM-supSubCls metric
values for each dataset. Based on the relative accuracy improvement, whether
the cGAN-augCls pipeline works or not is also denoted. Note that the cGAN data
augmentation only works when the SSIM-mergeCls values are smaller than
threshold 0.1319, or for the SSIM-supSubCls smaller than threshold 0.1652.

We further quantify the relationship between SSIM-supSubCls values and GM-
augCls relative accuracy improvement in Table 5. As shown in Figure 7, the
top1 validation accuracy increment decays exponentially with respect to the
metric values, and this exponential function can be fitted as:

$\hat{f}(x)=0.94^{202.74x-79.92}$ (4)

With this exponential curve fitted, one can easily predict the expected
accuracy improvement for any image dataset from its SSIM-supSubCls value.
Table 6 provides goodness-of-fit ($R^{2}$) and Mean Absolute Error (MAE)
measurements for the function $f$. The high $R^{2}$ and low MAE values show
that the formulation of $f$ is highly effective on modeling the relationship
between SSIM-supSubCls and accuracy improvement with our proposed data
augmentation pipeline.

Figure 7: Scatter plot and curve fitted for dataset SSIM-supSubCls values vs GM-augCls accuracy improvements for class-conditional StyleGAN2 and Guided Diffusion model trained on iNaturalist-2019, flowers, UTKFace and scene (calculated from Table 5). Regardless of model architecture or dataset, the results show a common exponential decay trend. Model | $R^{2}_{f}$ | MAEf(%)1
---|---|---
cGAN-augCls | 0.8749 | 4.7882
GD-augCls | 0.9597 | 5.5035
1 Here MAE is short for Mean Absolute Error
Table 6: Goodness-of-fit $R^{2}$ and Mean Absolute Error (MAE) measurements
for the SSIM-supSubCls vs GM-augCls function $f$.

Table 7 compares the state-of-the-art (SOTA) classification validation
accuracy from [14] and ours on the whole iNaturalist-2019 dataset. From this
table, our results with Masked Autoencoder (MAE) is comparable with the SOTA
one, even though the SOTA is with $448\times 448$ while ours is with
$128\times 128$ input image resolutions which largely reduce the need of
running time and computational resources.

SOTA 1 | Original Acc | cGAN-augCls Acc
---|---|---
ResNet18 | MAE | ResNet18 | MAE
88.3% | 54.4% | 83.1% | 55.4% | 82.5%
1 State-of-the-art (SOTA) classification validation accuracy with Masked
Autoencoder ViT-H448 [14]
Table 7: Top1 classification validation accuracy compared the SOTA and ours on
the whole iNaturalist-2019 dataset.

##  5 Conclusion and Discussion

We propose a metric called Super-Sub Class Structural Similarity (SSIM-
supSubCls) to evaluate the image set class similarity serving as an indicator
of classification accuracy improvement after data re-balancing with deep
generative model. We also provide a new pipeline achieving data augmentation
efficiently for imbalanced image datasets, using cGAN or diffusion models and
ResNet or Masked Autoencoder (MAE) classifiers. With user controlling the
number of images generated for each sub-class, the original dataset can be re-
balanced with qualified images.

We applied our pipeline on imbalanced dataset iNaturalist-2019, flowers,
UTKFace and scene, evaluating their classification accuracy when trained on
the original and balanced dataset after augmentation. Experimental results
reveal that, the top1 validation accuracy increment decays exponentially with
respect to the SSIM-supSubCls values regardless of model architecture or
dataset. With this exponential curve fitted, one can easily predict the
expected accuracy improvement for any image dataset from its metric value.

## References

  * [1] Dataset flowers.  https://www.kaggle.com/datasets/alxmamaev/flowers-recognition.  Accessed: 2021-11-04.
  * [2] Dataset scene.  https://www.kaggle.com/datasets/nitishabharathi/scene-classification.  Accessed: 2019-10-14.
  * [3] Dataset utkface.  https://www.kaggle.com/datasets/jangedoo/utkface-new.  Accessed: 2019-10-03.
  * [4] Antreas Antoniou, Amos Storkey, and Harrison Edwards.  Data augmentation generative adversarial networks, 2018.
  * [5] Paula Branco, Luís Torgo, and Rita P. Ribeiro.  A survey of predictive modelling under imbalanced distributions.  CoRR, abs/1505.01658, 2015.
  * [6] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer.  Smote: Synthetic minority over-sampling technique.  Journal of Artificial Intelligence Research, 16:321–357, Jun 2002\.
  * [7] Junya Chen, Zidi Xiu, Benjamin Goldstein, Ricardo Henao, and Lawrence Carin.  Supercharging imbalanced data learning with energy-based contrastive representation transfer.  In Advances in Neural Information Processing Systems 35, 2021.
  * [8] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie.  Class-balanced loss based on effective number of samples.  In CVPR, 2019.
  * [9] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [10] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8780–8794. Curran Associates, Inc., 2021.
  * [11] Fabio Henrique Kiyoiti dos Santos Tanaka and Claus Aranha.  Data augmentation using gans, 2019.
  * [12] gvanhorn38.  inaturalist 2019 competition.  https://github.com/visipedia/inat_comp, 2019.
  * [13] Haibo He, Yang Bai, Edwardo A. Garcia, and Shutao Li.  Adasyn: Adaptive synthetic sampling approach for imbalanced learning.  In 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), pages 1322–1328, 2008.
  * [14] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  arXiv:2111.06377, 2021.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  arXiv preprint arXiv:1512.03385, 2015.
  * [16] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6840–6851. Curran Associates, Inc., 2020.
  * [17] Ziyu Jiang, Tianlong Chen, Ting Chen, and Zhangyang Wang.  Improving contrastive learning on imbalanced data via open-world sampling.  In Advances in Neural Information Processing Systems 35, 2021.
  * [18] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of stylegan.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8110–8119, 2020.
  * [19] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu.  Large-scale long-tailed recognition in an open world.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [20] Giovanni Mariani, Florian Scheidegger, Roxana Istrate, Costas Bekas, and Cristiano Malossi.  Bagan: Data augmentation with balancing gan, 2018.
  * [21] Utkarsh Ojha, Krishna Kumar Singh, Cho-Jui Hsieh, and Yong Jae Lee.  Elastic-infogan: Unsupervised disentangled representation learning in class-imbalanced data.  In Advances in Neural Information Processing Systems 34, 2020.
  * [22] Mohamad Shahbazi, Martin Danelljan, Danda Pani Paudel, and Luc Van Gool.  Collapse by conditioning: Training class-conditional GANs with limited data.  In International Conference on Learning Representations, 2022.
  * [23] Junjiao Tian, Yen-Cheng Liu, Nathaniel Glaser, Yen-Chang Hsu, and Zsolt Kira.  Posterior re-calibration for imbalanced datasets.  Advances in Neural Information Processing Systems 34, 2020.
  * [24] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie.  The inaturalist species classification and detection dataset.  Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [25] Zhou Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli.  Image quality assessment: from error visibility to structural similarity.  IEEE Transactions on Image Processing, 13(4):600–612, 2004.
  * [26] Zhou Wang, Alan C. Bovik, and Ligang Lu.  Why is image quality assessment so difficult?  In 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 4, pages IV–3313–IV–3316, 2002.
  * [27] Shixian Wen, Amanda Sofie Rios, Kiran Lekkala, and Laurent Itti.  What can we learn from misclassified imagenet images?, 2022.


# Multi-agent simulation of voter’s behaviour

Albin Soutif Carole Adam Sylvain Bouveret
Univ. Grenoble-Alpes, Grenoble Informatics Laboratory

(_This is an internship report originally written in June 2018 by A. Soutif,
ENSIMAG intern_
_under the supervision of C. Adam and S. Bouveret_ )

###### Abstract

The goal of this paper is to simulate the voters’ behaviour given a voting
method. Our approach uses a multi-agent simulation in order to model a voting
process through many iterations, so that the voters can vote by taking into
account the results of polls. Here we only tried basic rules and a single
voting method, but further attempts could explore new features.

Keywords: Computational social choice, Iterative voting, multi-agent
simulation

##  1 INTRODUCTION

A voting process involves the participation of many people that interact
together in order to reach a common decision. In this paper, we focus on
voting processes in which a single person is elected. A voting method is
defined as the set of rules that determine the winner of the election, given
an input from each voter, for example their preferred candidate or an order
relation between all candidates. Social Choice Theory is the field that
studies the aggregation of individual preferences towards a collective choice,
like for example electing a candidate or choosing a movie. Computational
social choice is a recent field which aim is to apply computer science to
social choice problems [3]. Here we aim to design a multi-agent simulation in
order to study the collective decision process involved in an election.

A multi-agent simulation is a simulation in which we make several autonomous
agent interact with each other in a defined environment. The goal of this kind
of simulation is to study the global behaviour emerging from the local actions
of the agents [4, 6, 5]. There are only a few attempts to mix the field of
multi-agent simulation and computational social choice to model a voting
process, and that is the kind of approach we use in this paper. The goal of
this approach is to study the dynamics of voting methods through many
iterations. Here, we will focus on one particular voting method which is
plurality voting. In this method, voters vote for only one candidate and the
winner of the election is the candidate with the most votes.

Our approach was supported by the results of a study on the French
presidential election of 2017 [7]. In this study, people were asked to vote
with different voting methods, and to tell for whom they officially voted. The
goal of this study was to better understand the properties of several voting
methods. Among these voting methods, one in particular helped to build this
model, because it gave a precise insight of voters’ voting intentions (not
just their favourite candidate), it is the continuous evaluation method. In
this method, a voter gives a mark between 0 and 100 to each of the 11
candidates. Thanks to this study, we had access to over 30 000 of these
continuous evaluations, which helped us initialise our model.

A voting process can be modelled intuitively as a multi-agent system. Indeed,
voters and candidates can be modelled as autonomous agents, the real world, or
the internet, is the environment in which these agents evolve, and the
political debates, polls, conversations … Are the interactions which can
influence their final decision. In a multi-agent simulation, it is reasonable
to limit ourselves to a simpler model, in which the agents evolve in a limited
environment and have much simpler interactions with each other. Otherwise it
would be too difficult to model, to interpret, and too computationally
expensive.

First we will review the state of the art in this field (Section 2), then we
will present the way we built our model (Section 3), then our results along
with our interpretation (Section 4), and eventually we will conclude and
discuss some possible extensions of the model (Section 5).

##  2 STATE OF THE ART

Some interesting attempts have been made at building voting process models.
Here we will review the ones that inspired us the most in building our model.

###  2.1 Static models

A static simulation has been made by Ka-Ping Yee [10] in which the voters are
modelled by 2-dimensional points. In this simulation a normal distribution of
voters is drawn around every point, and each point is coloured according to
the candidate that won the election with that distribution of voters. The
conclusion of these simulations highlighted the different behaviours of some
voting rules.

###  2.2 Iterative models

Airiau et al. [1] attempted to model the outcome of an election where voters
could react strategically by learning from the others and trying to react in
order to maximise an utility function. The authors found out that for a given
set of rule and a precise methodology, the outcome was convergent and had good
mathematical properties. The drawback is that for the convergence to be
certain, the voters had to vote one by one and know at each step which
candidate was winning, which is not a realistic procedure.

Another attempt has been made for educational purpose by a network of
researchers in multi-agent simulation (MAPS) [2]. They made a multi-agent
simulation called “the Iznogoud model”, with simple interactions between
2-dimensional agents. The interactions used were local (each voter directly
influenced its surroundings), whereas in our model there are no local
interactions because we only focused on the global effect of polls, and not on
the effect of local interactions such as political conversations between
individuals. Also in the Iznogoud model, the voters were initialised randomly,
making it impossible to compare the results to any real case scenario.

In both the approaches from Ka-Ping Yee [10] and the Iznogoud simulation [2],
the voters are placed in a 2-dimensional space. In Ka-Ping Yee simulation the
model is not dynamic, so such a model would not help us study the dynamics of
voting methods. In the Iznogoud simulation, the interactions between voters
are local and very simple, and the model is initialised with a random
population of voters. In our model, we will try to integrate interactions that
are more realistic, and to initialise the population of agents with the help
of the results of the ”voter autrement” experimentation [7].

##  3 OUR MODEL

We choose to model each voter as a point in a 11 dimensional space, and we
initialise the model with the study’s continuous evaluation results, giving as
coordinates to a voter the marks he has given to the different candidates.
Because we also know the official vote of each voter, we integrate the
candidates into that space by taking the centroids of their voter’s continuous
evaluation. The model is dynamic and at each iteration, the voters move and
then a plurality vote is computed. To compute this vote, we make each voter
vote for the closest candidate from him and the candidate with the most votes
is the winner. In order to make the agents interact between each other, we use
polls that give information to everyone on the current plurality vote outcome.
The voter compute their move taking into account the results of the last poll.
That’s the way the agents interact between each other.

The model ran with different set of utility functions and agent behaviour.
Basically, we make each agent move with a velocity vector computed at each
iteration, and several methods were used to compute this one. We will discuss
those methods and their expected properties in this section.

###  3.1 Formal notations

Formally, we note as $V_{i}$ the set of voters at iteration $i$, and $C$ the
(static) set of candidates. Both of these sets contain a finite number of
11-dimension vectors. Thus $v_{k,i}$ is the position of voter $v_{k}$ at
iteration $i$. $s_{i}$ is the last poll available at iteration $i$, also
represented as an 11-dimension vector, containing the number of votes for each
candidate in the poll’s sample.

$V(v_{k,i},s_{i})$ is the velocity vector of voter $v$, knowing its current
position and the result of the last poll. At each iteration, the next position
vector of each voter $v_{k,i+1}\in V_{i+1}$ is given by the equation (1), as
the sum of its previous position and its velocity vector computed from this
position and the last poll.

$v_{k,i+1}=v_{k,i}+V(v_{k,i},s_{i})$ (1)

###  3.2 Utility functions

Before introducing the movement rules of our model, we introduce the concept
of utility function that we will later use in these rules. A utility function
is defined for each voter, as the utility a candidate would have for this
voter if he was elected. We define a utility function
$u:\mathbb{R}^{11}\times\mathbb{R}^{11}\rightarrow\mathbb{R}$, giving for the
first point (a voter) the utility that the second point (a candidate) would
have if winning the election. In practice, we will use $u(v_{k,i},c)$ for
$v_{k,i}\in V_{i}$ and $c\in C$.

In our model, we want that utility function to be in line with the fact that
the voters vote for the closest candidate from them. So intuitively, the
closer a voter is to a candidate, the more he likes him. The main property
that we want from these functions is that they are decreasing functions of the
distance between the voter and the candidates, and that they are not linear
(to model that some voters are strongly attached to a candidate).

Noting $dist(v,c)$ the Euclidean distance between voter $v$ and candidate $c$,
we designed 2 different utility functions representing different reasoning.
The first utility function given by equation (2) below simply expresses
utility as inversely proportional to the distance with the candidate.

$u:v,c\rightarrow\frac{1}{dist(v,c)}$ (2)

The second utility function that we designed also models the fact that a voter
can be strongly opposed to a candidate when he is too far away from him
(further than a parameter $\alpha$). In this case this utility function
becomes negative, ensuring that the voter will not get any closer to this
candidate (repulsion). This second function is given by equation (3) below.
The drawback is that some voters just flee away from the whole set of
candidates, which we model as abstention in the vote.

$u:v,c\rightarrow\frac{\alpha-dist(v,c)}{(1+dist(v,c))^{2}}$ (3)

###  3.3 Velocity computation

In this section we describe three techniques that can be used to compute the
velocity vector of the voters.

#### First approach: 3-pragmatist rule

A first approach is to use a rule described in [1] which is the three
pragmatist rule. This rule makes the voter vote for his favourite candidate
amongst the first three candidates of the election, which represent a
strategic vote for a candidate who has a chance to win. We integrate that in
our model by making each voter move towards this candidate, once given the
results of the last poll. The 3-pragmatist velocity vector towards candidate
$c$, the closest to voter $v_{k,i}$ among the first 3 candidates in results of
poll $s_{i}$, is given by the following equation:

$V(v_{k,i},s_{i})=e_{v_{k,i},c}$ (4)

where $e_{a,b}$ is the unit vector from point $a$ to $b$.

#### Second approach: maximum expected utility

A second approach is to use a utility function and to move toward the
candidate that maximises the expected utility. In order to approximate this
expectation, we use the poll results to compute a probability that each
candidate wins, given by the following equation as the proportion of expressed
votes in favour of this candidate.

$p(wins(c)|s_{i})=\frac{numberofvotesforcins_{i}}{totalnumberofvotesins_{i}}$
(5)

Once we have the probability that each candidate wins, computed from the
polls, the expected utility of their victory is the product of this
probability by the utility of them winning. This approximation gives a chance
even to candidates who have a small number of votes, provided that the utility
of them winning is high enough to compensate. On the contrary, other
approaches would just dismiss these candidates altogether, considering that
voting for them is useless because they have no chance to win in the end.

Thus we can compute the candidate selected by the voter as the one that
maximises this expected utility, as expressed by the following equation:

$c=argmax_{c\in C}[u(v_{k,i},c)*p(wins(c)|s_{i})]$ (6)

In the end the velocity vector is computed as the unit vector from voter
$v_{k,i}$ to that candidate $c$:

$V(v_{k,i},s_{i})=e_{v_{k,i},c}$ (7)

#### Third approach: personalised opinion centre

The third approach is different in the sense that rather than moving towards a
single candidate, it makes the voter move towards a personalised opinion
centre. In this approach we compute velocity as a linear combination of the
expected utilities of the different candidates, as expressed by the following
equation.

$V(v_{k,i},s_{i})=\sum_{c\in C}e_{v_{k,i},c}*u(v_{k,i},c)*p(wins(c)|s_{i})$
(8)

Since movement towards each candidate is weighed by the expected utility of
that candidate, we can expect that this vector will somehow be pointing in a
direction that will make the voter closer to the candidate that maximises its
expected utility.

##  4 RESULTS

###  4.1 Visualization

In order to visualise the multi-agent model behaviour, we choose to use
dimensionality reduction techniques. Two of them were tested, PCA (Principal
Component Analysis, [9]) and T-SNE (t-distributed stochastic neighbor
embedding, [8]). We choose PCA because it is less computationally expensive
and is not stochastic. The PCA results on initialisation of the model are
shown on Figure 1.

Figure 1: Principal Component Analysis to initialise the model

###  4.2 Parameters

Before presenting the results, we will review the set of parameters used and
the circumstances of the simulations. The simulations were ran on a sample of
1000 voters which are drawn among the 30000 voters who took part in the “Voter
Autrement” experiment. We will use the same seed for the random generator for
this sample to allow reproducibility of the experiments. We have defined above
two utility functions and three velocity formulas that can be tested. We are
not going to present nor simulate all the combinations, but we will rather
focus on the most interesting ones, and try to identify the impact of the
parameters on the simulation.

Below are the official votes given by the sample’s voters. Compared to the
actual results of the 2017 presidential election, it is clearly not
representative, but it will still be interesting to compare those results to
the outputs of our model.

  * •

Jean-Luc Melenchon 403

  * •

Jean Lassalle 7

  * •

François Asselineau 5

  * •

Nicolas Dupont-Aignan 11

  * •

François Fillon 34

  * •

Benoit Hamon 144

  * •

Philippe Poutou 12

  * •

Emmanuel Macron 200

  * •

Marine Le Pen 18

  * •

Nathalie Arthaud 3

  * •

Jacques Cheminade 2

###  4.3 Three-pragmatist rule

We tried the three-pragmatist velocity rule with different poll results. We
can see that this rule is very sensitive to the order of candidates given by
the poll (because it only draws electors towards the first three candidates in
the results of the poll).

Indeed, with a poll giving Nathalie Arthaud above Emmanuel Macron (Figure 2,
the voters closer to Macron (who is not in the top 3) move toward their
closest candidate among the three winners, in this case Benoit Hamon. This
leads to Hamon winning the election against Jean-Luc Melenchon.

Figure 2: With a poll where Nathalie Arthaud is above Emmanuel Macron

On the contrary, if the order in the poll results is the actual order (Macron
above Arthaud), the real order is just confirmed by the next iterations
(Figure 3).

Figure 3: With a poll where Emmanuel Macron is above Nathalie Arthaud

This rule gives accurate results regarding the actual official votes of our
sample, but only for the first three candidates of the poll. It also gives
totally wrong results if the poll order is not the same as the actual order.
In fact, some people behave in such a way that they will not change their
vote, even if their candidate has no chance to win at all. Explanations can be
a desire to show contestation, or a strong attachment to this candidate and
their ideas.

###  4.4 Maximum expected utility

In our next experiment, we used our second expected utility function and one
poll, and computed velocity with the second technique, of maximising expected
utility. Results are shown on Figure 4.

Figure 4: with utility function (2) and one poll

In this experiment, Emmanuel Macron has nearly as many votes as expected in
the sample. However, the utility function still needs to be tuned, because all
the voters who initially preferred Benoit Hamon, reported their votes (after
the poll) towards Jean-Luc Melenchon, which is not the case in the real sample
results. One explanation is that our expected utility model is imperfect;
indeed, people have a non-objective way of thinking in this situation, and
this is hard to model in a homogeneous way.

###  4.5 Utility speed (c)

In the next scenario, we used the third velocity formula, that moves voters
towards a personalised opinion centre. We compared the results obtained with
our 2 utility functions, and also with a single poll or regular polls along
the campaign.

Figure 5 illustrates the results with utility directly inversely proportional
to distance (first formula), and one single poll. In this figure, the number
of votes for Jean-Luc Melenchon is accurate, but Emmanuel Macron’s votes are
too low.

Figure 5: With utility function (1) and one poll

With that same utility function, regular polls do not greatly change the
results (Figure 6). We can observe nearly the same behaviour as in the
previous figure, even though we updated the information available to the
agents every 20 iterations.

Figure 6: with utility function (1) and one poll every 20 iteration

Finally we also tested the second utility function introducing repulsion
towards candidates that are too far, still with regular update polls. In
Figure 7 the results are much more tied, but they are also less accurate with
respect to the actual official votes of the sample. It is also hard to
conclude on a final order in this case, given that the rule does not converge.

Figure 7: With utility function (2) and one poll every 20 iteration

###  4.6 Periodicity of polls

The simulations run show that periodical polls do not fundamentally change the
result of the election. Indeed, quite often the results of the polls (here
made on 10% of the total population) are consistent with the order of the real
results, so the movement tendency and the order of candidates are just
confirmed a bit more by each new poll. And whenever a poll gives a different
order, it is often counter-balanced by the next poll.

However, in a real situation, other events can have an effect on the voters
preferences, such as media scandals (for instance the Penelope gate scandal
involving François Fillon during the French 2017 presidential elections, which
probably made him lose that election). In this case, even if some people are
not directly deterred from voting for their favourite candidate by the
scandal, they may be indirectly led to do so by strategy, if the subsequent
polls show that this candidate’s chance to win has dropped too much.

###  4.7 Notes about properties

The movement rules that we presented above were mainly built to make the
voters in the simulation behave somehow close to how the actual voters behave.
Because we focused on those properties, and did not make any mathematical
analysis of the rules, they do not necessarily have good mathematical
properties, in particular convergence.

It is hard to interpret the results if the simulations are not converging
towards at least a fixed order of the candidates, if not a fixed number of
votes. Indeed, we have no way to link the number of iterations in the
simulation to a real duration (in days), so any interpretation would remain a
strong supposition. The results presented here have been obtained after a
large number of iterations, when the electors are ”caught in a pit” and mainly
move towards one candidate, so that the order of the candidates does converge,
but the convergence of the number of votes is not guaranteed.

##  5 CONCLUSION AND OPENING

The models presented above have shown different interesting behaviours. The
one which gave the most accurate results is the simplest one, using the three-
pragmatist rule, even though it does not allow more than 3 candidates to
receive votes. To extend this approach it would be interesting to experiment a
k-pragmatist rule for different values of k, and play around it (maybe compute
a velocity vector using different k-pragmatist results).

The maximum expected utility rule should have really good properties, but the
utility functions were chosen quite arbitrarily. We struggled to accurately
compute an expected utility, because people do not really conduce complex
probabilistic calculus, and it is hard to model what really happens in
someones’ mind when making a voting decision. Many factors might play a role
such as emotions or cognitive biases. Also, the second utility function uses a
customisable $\alpha$ parameter to represent the tolerance before a voter is
repulsed by a candidate. Here we used the same $\alpha$ for each voter, but we
could also compute an individual value for each voter, as a function of his
starting position.

Finally, in this paper we only gave information to the voters through polls,
unique or recurrent, but more complex events could be modelled, as for example
media coverage of scandals, the use of social networks to communicate, or the
influence of other voters on each voter’s opinions.

## References

  * [1] Stéphane Airiau, Umberto Grandi, and Filipo Studzinski Perotto.  Learning agents for iterative voting.  In Rothe J., editor, International Conference on Algorithmic Decision Theory, volume 10576 of Lecture Notes in Computer Science, pages 139–152, Cham, 2017. Springer.
  * [2] Frédéric Amblard, Thomas Louail, Romain Reulier, Paul Salze, and Patrick Taillandier.  Modèle iznogoud : fiche pédagogique.  https://maps.hypotheses.org/production-pedagogique-de-maps/modeles-mapsiens/modele-iznogoud, 2014\.
  * [3] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia.  Handbook of computational social choice.  Cambridge University Press, New York, NY, USA, 1st edition, 2016.
  * [4] Joshua M Epstein and Robert Axtell.  Growing artificial societies: social science from the bottom up.  Brookings Institution Press, 1996.
  * [5] Charles M. Macal.  Everything you need to know about agent-based modelling and simulation.  Journal of Simulation, 10(2):144–156, 2016.
  * [6] Charles M. Macal and Michael J. North.  Tutorial on agent-based modelling and simulation.  Journal of Simulation, 4(3):151–162, 2010.
  * [7] CoCoRICo-CoDec project.  Experimentation voter autrement.  https://vote.imag.fr/, 2017.
  * [8] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  Journal of machine learning research, 9(11), 2008.
  * [9] Svante Wold, Kim Esbensen, and Paul Geladi.  Principal component analysis.  Chemometrics and intelligent laboratory systems, 2(1-3):37–52, 1987\.
  * [10] Ka-Ping Yee.  Voting simulation visualizations.  http://zesty.ca/voting/sim/, 2005.