# Learning to Aggregate and Refine Noisy Labels for Visual Sentiment Analysis

Wei Zhu  Zihe Zheng  Haitian Zheng  Hanjia Lyu  Jiebo Luo

###### Abstract

Visual sentiment analysis has received increasing attention in recent years.
However, the dataset’s quality is a concern because the sentiment labels are
crowd-sourcing, subjective, and prone to mistakes, and poses a severe threat
to the data-driven models, especially the deep neural networks. The deep
models would generalize poorly on the testing cases when trained to over-fit
the training samples with noisy sentiment labels. Inspired by the recent
progress on learning with noisy labels, we propose a robust learning method to
perform robust visual sentiment analysis. Our method relies on external memory
to aggregate and filters noisy labels during training. The memory is composed
of the prototypes with corresponding labels, which can be updated online. The
learned prototypes and their labels can be regarded as denoising features and
labels for the local regions and can guide the training process to prevent the
model from overfitting the noisy cases. We establish a benchmark for visual
sentiment analysis with label noise using publicly available datasets. The
experiment results of the proposed benchmark settings comprehensively show the
effectiveness of our method.

##  I Introduction

There is increasing attention in visual sentiment analysis driven by the need
for more and more people to share their feelings with images, emojis, and
other visual content. With the successes of deep neural networks in
conventional computer vision tasks, numerous methods have been proposed to
conduct visual sentiment analysis and have shown clear advantages over
traditional methods with handcrafted features [1].

However, there are several issues when applying deep neural networks to visual
sentiment analysis [2, 3]. The labels for visual sentiment analysis are
inherently subjective and error-prone since it can be confusing for humans to
recognize the sentiment of images [3]. The frequently mislabeled samples will
hinder the performance of deep models and cause the models to generalize
poorly on unseen cases. Several existing datasets are labeled by first
querying the search engine with keywords [4]. Although crowd workers were
employed to verify the labels data manually, the resulting labels still
contain a fair amount of noise. Therefore, it is critical to develop robust
methods to handle mislabeled samples explicitly.

This paper proposes a method called Aggregate and Refine Net (ARNet) to
mitigate the problem. ARNet is equipped with an external memory composed of
prototypes with corresponding pseudo labels. Basically, the prototypes are
optimized to be locality representative of the feature space and thus can work
as proxies to aggregate the labels of the samples that are close to them to
form prototype labels. With the help of the optimized memory, the proposed
method can learn to filter the noisy labels and provide a refined label for
each training sample. The key to our method is a strategy to read and write
the prototypes and the corresponding labels stored in the memory. More
specifically, we consider the input features as queries, prototypes as keys,
and prototype labels as values. We read the memory through the attention
addressing mechanism. The memory-guided labels for the training samples can be
retrieved from the memory and used to refine the noisy labels. For memory
updating, we write the memory in an online manner during training and update
the differentiable prototypes by gradient descent. Subsequently, the prototype
labels are updated in a momentum fashion. The refined labels obtained with the
external memory can thus guide us to build a more robust model for visual
sentiment analysis.

The main contributions of our paper are as follows:

  1. 1.

We establish a benchmark for visual sentiment analysis with label noise on
publicly available datasets to explicitly handle commonly existing noisy
sentiment labels.

  2. 2.

We address visual sentiment analysis with label noise using an Aggregate and
Refine Network (ARNet). ARNet aggregates and filters the noisy labels with an
external memory composed of prototypes with labels. The learned prototypes and
their labels can be regarded as denoising features and labels for the local
regions.

  3. 3.

The proposed ARNet achieves superior performance compared with the state-of-
the-art learning-with-noisy-labels methods on the established benchmark for
visual sentiment analysis with label noise.

Figure 1: Overview of the proposed method. We retrieve the pseudo labels for
the training samples according to the external memory through the attention
addressing mechanism. The memory comprises the prototypes and the
corresponding labels, which are updated during training. We give an example of
the latent space during training on the top left side. Stars denote the
prototypes stored in the memory, and other shapes are training samples.
Different classes are in different colors. The prototypes are updated by a
clustering objective (detailed in Sec. III-B) to be locality representative.
The prototype labels are obtained by aggregating the prediction of nearby
samples assigned to the prototypes and enabling the training samples to refine
their label by reading and modifying the memory mutually.

##  II Related Work

###  II-A Visual Sentiment Analysis

Early works on visual sentiment analysis are based on handcrafted features.
Machajdik and Hanbury [5] employed features from art and psychology theories
to define image features that are specific to the domain of artworks with
emotional expression. Borth et al. [6] proposed SentiBank, a detector library
containing 1,200 Adjective Noun Pairs (ANP). As a continuation of SentiBank,
Chen et al. [1] proposed DeepSentiBank, which uses convolutional neural
networks (CNNs) to determine which ANPs exist in an image and classify the
sentiment of images accordingly. You et al. pre-trained a CNN on a half-
million-image Flickr dataset [6] and used a progressive fine-tuning process to
transfer the knowledge to a smaller dataset [7]. Class Activation Maps(CAM)
[8] is a spatial heat map that shows the discriminative areas of an image in a
classification process. CAM-based methods have shown great potential in image
classification [9], as well as visual sentiment analysis. She et al. [10]
proposed a coupled network (WSCNet) that generates a sentiment CAM to couple
with the classification branch. However, little work has been conducted to
explicitly handle the noisy and subjective sentiment labels. NLWSNet [2] was
proposed to handle the problem by a non-extreme attention mechanism and a
special-class activation map module. However, their work lacked a comparison
with the existing methods of learning with noisy labels, and the settings are
also not realistic to some extent.

###  II-B Learning with Noisy Label

With the proliferation of content on the Internet, large-scale datasets can be
easily constructed. However, noisy labels are commonplace. Some previous works
show that simply applying supervised methods on weakly-labeled datasets cannot
fully exploit the information in such noisy datasets [11]. One of the
approaches to perform robust learning on datasets with noisy labels is
modifying the cross-entropy loss [12, 13]. Zhang and Sabuncu [12] proposed a
generalized cross-entropy loss, which is a generalization of the mean absolute
error (MAE) and categorical cross-entropy loss (CCE). Wang et al. [14] showed
that simple deep neural networks could overfit noisy labels while underfitting
hard labels and proposed Symmetric cross-entropy Learning (SL) to address both
problems. Knowledge distillation can also be used to refine noisy label [15].
Curriculum learning is also a possible method for robust learning [16, 17].
Jiang et al. [18] proposed MentorNet, which provides a curriculum for a
StudentNet to concentrate on the labels that are more likely to be clean. Co-
teaching [19] trains two networks that teach each other. In particular, they
select clean data in the training data, respectively, and feed the clean data
to the other network. Other methods take one step further and aim to correct
the noisy labels during training to exploit most of the data. Song et al. [20]
proposed SELFIE, which corrects refurbishable noisy data for an improvement in
the robustness of deep neural networks. DivideMix is another method proposed
to correct the noisy labels [21]. It first divides the clean and noisy data by
modeling their losses and then trains the network on the labeled (clean) data
and unlabeled (noisy) data. Since deep neural network models often fit the
clean labeled data first [22], Liu et al. [23] proposed a framework called
early-learning regularization (ELR), which first produces targets from the
model outputs and then regularizes the model towards the targets. In this
study, we propose to aggregate and filter noisy labels with external memory to
improve the performance for visual sentiment analysis with label noise.

##  III Our Method

The deep neural networks trained to fit the samples with noisy sentiment
labels will generalize poorly on testing cases, and we propose to utilize
external memory to aggregate learned knowledge and refine noisy labels. The
overview of our method is shown in Figure 1.

Given a training dataset $\\{(x_{i},y_{i})\\}_{i=1}^{N}$ as the input data and
the noisy labels from $K$ different classes, a low-dimensional representation
$h_{i}=f_{\theta}(x_{i})\in R^{d}$ is extracted by a network $f$ parameterized
by $\theta$. We also have a classifier implemented with a fully connected
layer parameterized by $\phi$, and the predication for the $i$-th sample is
denoted as $r_{i}$. Moreover, we denote the memory with $L$ slots as
$M=\\{C,G\\}=\\{c_{i},g_{i}\\}_{i=1}^{L}$, where $K\ll L$, $c_{i}$ is the
representation of memorized prototypes and $g_{i}\in R^{K}$ is the
corresponding soft label.

The primary motivation of our method is to aggregate the learned knowledge
into the memory and retrieve a refined label from memory for each sample. We
update the prototypes and the corresponding labels to represent a set of
samples in a local region of the feature space. The learned prototypes and
their labels can be regarded as denoising features and labels for the local
regions. They can guide the training process to alleviate the influence of
noisy labels. One of the critical parts of our method is updating the memory,
which we describe in the following section.

###  III-A Memory Reading for Training with Prototype Labels

We first describe how to read the memory by supposing that there is a memory
composed of the prototypes with soft labels used to store the knowledge of the
previous training process. We will describe the memory writing rules later in
Section III-B.

Given the $i$-th training sample, we denote its current prediction as $r_{i}$
and the latent representation as $h_{i}$. Its pseudo label $t_{i}$ is obtained
with the memory as

$\begin{split}{t_{i}}=(1-\lambda)&r_{i}+\lambda v_{i},\\\
v_{i}=\sum_{j}^{L}{p_{i,j}g_{j}}=&\sum_{j}^{L}{\frac{\exp(s(h_{i},c_{j}))}{\sum_{l}^{L}\exp(s(h_{i},c_{l}))}g_{j}}\end{split}$
(1)

where $s(h_{i},c_{j})$ is the cosine similarity between the latent
representation of $i$-th sample and $j$-th prototype, and
$p_{i,j}=\frac{\exp(s(h_{i},c_{j}))}{\sum_{l}^{L}\exp(s(h_{i},c_{l}))}$. The
pseudo label $t_{i}$ is a weighted average between the current prediction
$r_{i}$ and the memory-retrieved soft label $v_{i}$. $\lambda\in[0,1]$
controls the trade-off. It is worth noting that if we set $\lambda=1$ to
discard the external memory, this process will be transformed into Bootstrap
[24] and ELR [23]. The memory-retrieved label $v_{i}$ is obtained with the
attention addressing mechanism by considering the $i$-th sample representation
$h_{i}$ as the query, the prototype representation $c_{j}$ as the key, and the
prototype label $g_{j}$ as the value. Briefly, we first conduct the softmax
between query $h_{i}$ and key $c_{j}$, and then use the obtained address to
retrieve the label stored in label memory $v$.

With the obtained pseudo label $t_{i}$ and the given label $y_{i}$, we update
our model by minimizing the objective as:

$\min L_{ce}(r_{i},y_{i})+\frac{\alpha}{N}\sum_{i}^{N}\log(1-r_{i}^{T}t_{i}),$
(2)

where $\alpha$ is a hyperparameter and is set as $\alpha=3$. The first term is
a commonly used cross-entropy loss for the current prediction $r_{i}$ and
given label $y_{i}$. We follow the work of Liu et al. [23] to use the second
term to encourage the prediction $r_{i}$ to be close to the pseudo label
$t_{i}$.

###  III-B Memory Writing

We present how to update the memory $M$ in this section. The memory $M$,
composed of the prototypes with the soft labels, plays a crucial role in our
method, and a desirable set of prototypes should be representative of local
regions. We basically rely on deep clustering methods to achieve this goal. We
adopt the clustering method proposed by [25] to encourage the assignment
matrix to approximate target indicator matrix. For detail, given $N$ training
samples, we update the prototypes by minimizing

$\min_{P}-\frac{1}{N}\sum_{i}^{N}\sum_{j}^{L}q_{i,j}\log p_{i,j}.$ (3)

where $p_{i,j}$ is from the assignment matrix and defined in Eq. (1), and
$q_{i,j}$ is from the target indicator matrix $Q\in R^{N\times L}$ which is
obtained by optimizing the following objective [26, 27]:

$\max_{Q}Tr(QC^{T}H)-\xi\sum_{i}^{N}\sum_{j}^{K}Q_{i,j}\log Q_{i,j},$ (4)

where $H=\\{h_{1},h_{2},\dots,h_{N}\\}\in R^{d\times N}$ is the matrix of the
latent representation for the training data, and
$C=\\{c_{1},c_{2},\dots,c_{N}\\}\in R^{d\times L}$ is the prototype matrix.
$\xi$ is a hyperparameter and is set to 0.05 following [27]. Eq. (4) is used
to obtain target indicator matrix $Q$ and works similarly as the expectation
step of Expectation Maximization while Eq.(3) is similar to the maximization
step. The $Q$ is optimized to make the trace of the multiplication between
reconstructed data representation $QC^{T}$ and original representation $H$
maximized. For each minibatch iteration, we first solve Eq. (4) to obtain $Q$
and then encourage $P$ to approximate $Q$ by optimizing Eq. (3). We perform
end-to-end training through $P$ as it is computed from the latent
representation and block the back-propagation through $Q$ [27, 25]. To
accommodate Eq. (4) for the mini-batch training, we cache 1K features [27,
25].

In the end, we update the prototype label $g_{j}\in R^{K}$ for the $j$-th
prototype in a momentum fashion, and $g_{j}$ is updated to aggregate and
memorize the previous predictions of the samples assigned to it as

$g_{j}=\beta g_{j}+(1-\beta)\sum_{i}q_{i,j}r_{i},$ (5)

where $\beta$ is the momentum factor and we set $\beta=0.8$. As shown in Eq.
(5), $g_{j}$ is updated with the average of the predictions of the samples
assigned to it.

Input: the training set: $\mathcal{D}=\\{(x_{i},y_{i})|x\in
R^{d_{x}},y\in\\{0,\cdots,K-1\\}\\}^{N}_{i=1}$

Input: memory slot $L$

Output: the trained weight $\theta,\phi$

/* Model initialization */

initialize $C$ with an orthogonal matrix;

/* Main loop */

while  _the maximal iterations are not reached_ do

$x,y\sim\mathcal{D}$

// sample training data

/* Prepare for Memory Reading */

$v_{i}\leftarrow\sum_{j}^{L}{\frac{\exp(s(h_{i},c_{j}))}{\sum_{l}^{L}\exp(s(h_{i},c_{l}))}g_{j}}$

// retrieve pseudo label from memory

${t_{i}}\leftarrow(1-\lambda)r_{i}+\lambda v_{i}$

// generate pseudo label (Eq. 1)

/* Prepare for Memory Writing */

$Q\leftarrow\arg\max_{Q}Tr(QC^{T}H)-\xi\sum_{i}^{N}\sum_{j}^{K}Q_{i,j}\log
Q_{i,j},$

// update the target indicator matrix (Eq. 4)

/* Model update */

$\theta,\phi,C\leftarrow\arg\min_{\theta,\phi,C}L_{ce}(r_{i},y_{i})+\frac{\alpha}{N}\sum_{i}^{N}\log(1-r_{i}^{T}t_{i})-\frac{1}{N}\sum_{i}^{N}\sum_{j}^{L}q_{i,j}\log
p_{i,j}$

// (Eq. 6)

/* Prototype label update */

$g_{j}=\beta g_{j}+(1-\beta)\sum_{i}q_{i,j}r_{i},$

// update the prototype label (Eq. 5)

end while

Algorithm 1 Training algorithm.

###  III-C Overall Training and Inference

We summarize the whole training procedure of our method as follows. We
initialize the prototype with an orthogonal matrix and update it with
backpropogation. For each iteration, we first simultaneously update the
network, classifier, and memorized prototypes by minimizing Eq. (2) and Eq.
(3) as

$\min
L_{ce}(r_{i},y_{i})+\frac{\alpha}{N}\sum_{i}^{N}\log(1-r_{i}^{T}t_{i})-\frac{1}{N}\sum_{i}^{N}\sum_{j}^{L}q_{i,j}\log
p_{i,j}.$ (6)

Second, we update the pseudo labels for prototypes by Eq. (5). We use the
feature extractor and the classifier to conduct sentiment classification
during inference. We summarize the training detail in Alg. (1).

Figure 2: Example images from the F&I dataset.

##  IV Experiments

###  IV-A Datasets

We evaluate our method on publicly available datasets including Flickr and
Instagram (F&I) [4], Emotion6 [28], ARTphoto [29], and UnBiasedEmo [30]. The
F&I dataset is obtained by querying Flickr and Instagram and contains 21,828
images in total. Emotion6 is retrieved from Flickr with 1,980 images in six
sentiment categories. ARTphoto is constructed by 807 images retrieved from an
art sharing site, where we convert the task to binary classification
(positive/negative). UnBiasedEmo contains about 3000 images from Google in 6
categories. We summarize the statistics of all the datasets in Table I.

TABLE I: Summary of the datasets. Dataset | Size | Labeling
---|---|---
F&I [4] | 23,308 |  | Awe, amusement, contentment,
---
excitement, disgust, anger, fear, sad
Emotion6 [28] | 1,980 | Anger, disgust, fear, joy, sadness, surprise
ArtPhoto [29] | 807 |  | Pos, Neg
---
UnBiasedEmo [30] | 3,045 | Anger, fear, joy, love, sadness, surprise
TABLE II: Results on Emotion6 (the best results are highlighted in bold). Methods | SentiBank | $\epsilon=0.2$ | $\epsilon=0.3$ | $\epsilon=0.4$
---|---|---|---|---
ACC | F1 | ACC | F1 | ACC | F1 | ACC | F1
Baseline | 0.4369 | 0.4102 | 0.4874 | 0.4765 | 0.4548 | 0.4496 | 0.4167 | 0.4114
Bootstrap [24] | 0.4470 | 0.4210 | 0.5000 | 0.4912 | 0.4798 | 0.4695 | 0.4268 | 0.4150
GSE [31] | 0.4621 | 0.4342 | 0.5000 | 0.4851 | 0.4666 | 0.4557 | 0.4313 | 0.4253
SL [14] | 0.4646 | 0.4359 | 0.4975 | 0.4861 | 0.4722 | 0.4457 | 0.4261 | 0.4146
TCE [32] | 0.4672 | 0.4472 | 0.4848 | 0.4761 | 0.4343 | 0.4252 | 0.4596 | 0.4564
CT+ [33] | 0.4343 | 0.4143 | 0.5051 | 0.4899 | 0.4922 | 0.4793 | 0.4646 | 0.4584
MixUp [34] | 0.4619 | 0.4327 | 0.5278 | 0.5172 | 0.4672 | 0.4624 | 0.4545 | 0.4479
ELR [23] | 0.4571 | 0.4421 | 0.4949 | 0.4775 | 0.4848 | 0.4634 | 0.4192 | 0.4127
Ours | 0.4747 | 0.4486 | 0.5303 | 0.5144 | 0.5278 | 0.5127 | 0.4823 | 0.4714
TABLE III: Results on ArtPhoto (the best results are highlighted in bold). Methods | SentiBank | $\epsilon=0.2$ | $\epsilon=0.3$ | $\epsilon=0.4$
---|---|---|---|---
ACC | F1 | ACC | F1 | ACC | F1 | ACC | F1
Baseline | 0.6181 | 0.6151 | 0.6975 | 0.6966 | 0.679 | 0.6766 | 0.6235 | 0.6233
Bootstrap [24] | 0.6220 | 0.6194 | 0.7022 | 0.6981 | 0.6358 | 0.6355 | 0.6111 | 0.6077
GSE [31] | 0.6171 | 0.6114 | 0.6667 | 0.6667 | 0.6728 | 0.6728 | 0.6605 | 0.6599
SL [14] | 0.6296 | 0.6294 | 0.6975 | 0.6966 | 0.6667 | 0.6592 | 0.6420 | 0.6406
TCE [32] | 0.6235 | 0.6110 | 0.7184 | 0.7077 | 0.6975 | 0.6969 | 0.6852 | 0.6798
CT+ [33] | 0.6543 | 0.6530 | 0.7160 | 0.7133 | 0.6667 | 0.6648 | 0.6296 | 0.6291
MixUp [34] | 0.5988 | 0.5953 | 0.7043 | 0.7018 | 0.6958 | 0.6925 | 0.6914 | 0.6913
ELR [23] | 0.6296 | 0.6287 | 0.6852 | 0.6798 | 0.6728 | 0.6692 | 0.6605 | 0.6594
Ours | 0.6675 | 0.6581 | 0.7222 | 0.7117 | 0.7099 | 0.7080 | 0.7037 | 0.7015

###  IV-B Experimental Settings and Evaluation Metrics

We run an ordinal cross-entropy classifier as the baseline, and additionally
compare the proposed ARNet with other learning-with-noisy-label methods
including Bootstrap [24], GSE [31], SL [14], TCE [32], CoTeaching+(CT+) [33],
MixUp [34], and ELR [23]. For ARNet, we set $\lambda=0.8$, $\beta=0.8$, and
search the number of memory slots from $\\{16,32,64,128\\}$.

TABLE IV: Results on UnBiasedEmo (the best results are highlighted in bold). Methods | $\epsilon=0.2$ | $\epsilon=0.3$ | $\epsilon=0.4$
---|---|---|---
ACC | F1 | ACC | F1 | ACC | F1
Baseline | 0.5419 | 0.5167 | 0.4614 | 0.4313 | 0.4072 | 0.3678
Bootstrap [24] | 0.5238 | 0.4937 | 0.4614 | 0.4321 | 0.4171 | 0.3871
GSE [31] | 0.5543 | 0.4800 | 0.5189 | 0.4934 | 0.4729 | 0.4000
SL [14] | 0.5222 | 0.4992 | 0.5140 | 0.4800 | 0.4417 | 0.3978
TCE [32] | 0.5649 | 0.5325 | 0.5189 | 0.4659 | 0.4154 | 0.3589
CT+ [33] | 0.5454 | 0.4568 | 0.4696 | 0.4156 | 0.4663 | 0.3940
MixUp [34] | 0.5419 | 0.5106 | 0.4778 | 0.4472 | 0.4401 | 0.4041
ELR [23] | 0.5419 | 0.5074 | 0.4729 | 0.4495 | 0.4548 | 0.3934
Ours | 0.5517 | 0.5184 | 0.5238 | 0.4867 | 0.4744 | 0.4108
TABLE V: Results on F1 (the best results are highlighted in bold). Methods | $\epsilon=0.2$ | $\epsilon=0.3$ | $\epsilon=0.4$
---|---|---|---
ACC | F1 | ACC | F1 | ACC | F1
Baseline | 0.5197 | 0.4722 | 0.4986 | 0.4207 | 0.4528 | 0.3977
Bootstrap [24] | 0.5588 | 0.5026 | 0.5014 | 0.4419 | 0.4647 | 0.3967
GSE [31] | 0.5765 | 0.4285 | 0.5619 | 0.4239 | 0.5307 | 0.3957
SL [14] | 0.5655 | 0.5117 | 0.5032 | 0.4527 | 0.5038 | 0.4372
TCE [32] | 0.5850 | 0.4518 | 0.5383 | 0.4385 | 0.4913 | 0.4337
CT+ [33] | 0.5481 | 0.4544 | 0.5307 | 0.4066 | 0.4922 | 0.3862
MixUp [34] | 0.5527 | 0.4860 | 0.5111 | 0.4597 | 0.4782 | 0.4140
ELR [23] | 0.5481 | 0.4833 | 0.5160 | 0.4449 | 0.4565 | 0.3863
Ours | 0.5887 | 0.5026 | 0.5655 | 0.4951 | 0.5337 | 0.4668

For Emotion6, ARTphoto, and Unbiased Emotion, we randomly split the dataset
into 80% training set and 20% testing set following previous work [10, 2]. For
F&I, we split the data into 80% training set, 5% validation set and 15%
testing set following [10]. We adopt an ImageNet pre-trained ResNet-34 as the
feature extractor [35], and use the Adam optimizer with a learning rate of
0.0001. The batchsize is set to 128 and we run all methods for 50 epoches for
these datasets. We first resize the images to 256x256, and then perform random
crop and random horizontal flip for data augmentation to obtain images of
224*224. We report accuracy and F1 scores on the testing set averaged over
three runs. We use PyTorch to implement ARNet, and all the experiments are run
on a Linux server with 4x2080Ti Graphical Cards.

We propose two different settings to simulate the mislabeled scenarios for
visual sentiment analysis. For the first scenario, we follow the conventional
settings for learning with noisy labels [19, 32, 23, 36], and symmetrically
flip labels for $\epsilon$ % of training samples. We vary
$\epsilon\in\\{0.2,0.3,0.4\\}$. We simulate a virtual agent with a weak
classifier and use the classification prediction as “pseudo” noisy labels for
the second scenario. We expressly adopt SentiBank with an SVM classifier as
the virtual agent. We train on the noisy label set for both settings and test
on the original dataset.

###  IV-C Experimental Results

The experimental results are shown in Tables II, III, IV, and V. We draw
several conclusions as follows. First, the results show that deep models in
learning with noisy labels can boost visual sentiment analysis performance
with label noise. For instance, our method achieves 5.3% improvements in terms
of accuracy compared with the baseline on Emotion6 on average, and 4.7% on
ArtPhoto. The encouraging results suggest that it is possible to train a
robust classifier for visual sentiment analysis with webly retrieved data.
Moreover, we note that the proposed visual sentiment benchmark can also work
as a benchmark suite to evaluate methods of learning with noisy labels.

(a) Baseline

(b) ELR

(c) Ours

Figure 3: TSNE visualization of the learned embedding for the baseline, ELR,
and our method on the F&I validation set. Circles denote latent
representations of the samples, and stars denote memorized prototypes.

TABLE VI: Results on F&I with different number of memory slots. $L$ | 16 | 32 | 64 | 128
---|---|---|---|---
ACC | 0.5195 | 0.5314 | 0.5655 | 0.5714
F1 | 0.4512 | 0.4683 | 0.4951 | 0.4983

TABLE VII: Results on UnBiasedEmo with different number of memory slots. $L$ | 16 | 32 | 64 | 128
---|---|---|---|---
ACC | 0.4762 | 0.4975 | 0.5238 | 0.4992
F1 | 0.4400 | 0.4511 | 0.4867 | 0.4656

Second, the proposed ARNet consistently outperforms the state-of-the-art
methods for handling noisy sentiment labels, for example, about 2.7%
improvement on F&I and 2.1% on ArtPhoto in terms of average accuracy, which
demonstrates ARNet can learn more discriminative and informative
representation with the proposed external memory. The memory also allows the
training samples to share and mutually refine their noisy labels. We validate
this point by visualizing the latent representation obtained by different
models in Fig. 3, where the visualization results directly show that the
proposed ARNet could learn to aggregate and refine noisy labels via the
external memory and the locality representative prototypes. Fig. 3 also
suggests that the learned representations of ARNet are optimized to have small
intra-class distance and large inter-class distance, which should be
attributed to the fact that we jointly conduct prototype optimization and
noisy label refining in Eq. (6). The excellent property of the learned
representation directly leads to better performance by ARNet compared with
other methods.

Finally, by comparing two different scenarios for visual sentiment analysis
with label noise, the proposed “virtual” agent by the SentiBank sentiment
classifier brings more challenges to existing methods as the mislabeled
samples by the “virtual” agent is more challenging and more confusing. Our
method also achieves superior performance in the virtual agent setting. For
example, the proposed ARNet achieves more than 1.3% and 0.5% performance gain
in terms of accuracy and F1 score, respectively, on the ArtPhoto dataset.

###  IV-D Ablation Study

In this section, we conduct experiments to study the influence of the hyper-
parameters on F&I and UnBiasedEmo with $\epsilon=0.3$. We vary the number of
memory slots from $\\{16,32,64,128\\}$, and the results are shown in Table VII
and Table VII, respectively. The results conclude that better performance can
be expected with an increasing number of memory slots, and the incremental
improvements will be negligible when the memory slots are large enough. For
example, for UnBiasedEmo, it seems that 64 prototype slots are adequate, and
128 prototype lots may lead to an overfitting problem.

##  V Conclusions

This paper presents ARNet to handle label noise in visual sentiment analysis.
ARNet utilizes an external memory to aggregate and filter the noisy labels and
provide refined labels for training samples. Moreover, we propose reading the
memory through attention addressing mechanism and updating the memory to have
the stored prototypes be locality representative. The prototype labels can be
used to aggregate and refine the labels for samples in the local region of the
feature space. The learned prototypes and labels can be regarded as denoising
features and labels for the local regions. We establish a benchmark for visual
sentiment analysis with label noise using publicly available datasets, and our
experiments show the effectiveness of our method the proposed benchmark.

## References

  * [1] T. Chen, D. Borth, T. Darrell, and S. Chang, “Deepsentibank: Visual sentiment concept classification with deep convolutional neural networks,” _ArXiv_ , vol. abs/1410.8586, 2014.
  * [2] L.-y. Xue, Q.-r. Mao, X.-h. Huang, and J. Chen, “Nlwsnet: a weakly supervised network for visual sentiment analysis in mislabeled web images,” _Frontiers of Information Technology & Electronic Engineering_, vol. 21, no. 9, pp. 1321–1333, 2020.
  * [3] J. Yang, D. She, Y.-K. Lai, P. L. Rosin, and M.-H. Yang, “Weakly supervised coupled networks for visual sentiment analysis,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 7584–7592.
  * [4] Q. You, J. Luo, H. Jin, and J. Yang, “Building a large scale dataset for image emotion recognition: The fine print and the benchmark,” in _AAAI_ , 2016\.
  * [5] J. Machajdik and A. Hanbury, “Affective image classification using features inspired by psychology and art theory,” _Proceedings of the 18th ACM international conference on Multimedia_ , 2010.
  * [6] D. Borth, T. Chen, R. Ji, and S. Chang, “Sentibank: large-scale ontology and classifiers for detecting sentiment and emotions in visual content,” in _MM ’13_ , 2013.
  * [7] Q. You, J. Luo, H. Jin, and J. Yang, “Robust image sentiment analysis using progressively trained and domain transferred deep networks,” in _AAAI_ , 2015\.
  * [8] B. Zhou, A. Khosla, À. Lapedriza, A. Oliva, and A. Torralba, “Learning deep features for discriminative localization,” _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 2921–2929, 2016.
  * [9] Y. Zhu, Y. Zhou, Q. Ye, Q. Qiu, and J. Jiao, “Soft proposal networks for weakly supervised object localization,” _2017 IEEE International Conference on Computer Vision (ICCV)_ , pp. 1859–1868, 2017.
  * [10] D. She, J. Yang, M.-M. Cheng, Y.-K. Lai, P. L. Rosin, and L. Wang, “Wscnet: Weakly supervised coupled networks for visual sentiment classification and detection,” _IEEE Transactions on Multimedia_ , vol. 22, pp. 1358–1371, 2020\.
  * [11] J. Li, C. Xiong, and S. Hoi, “Mopro: Webly supervised learning with momentum prototypes,” _ArXiv_ , vol. abs/2009.07995, 2020.
  * [12] Z. Zhang and M. Sabuncu, “Generalized cross entropy loss for training deep neural networks with noisy labels,” in _NeurIPS_ , 2018.
  * [13] X. Ma, H. Huang, Y. Wang, S. Romano, S. Erfani, and J. Bailey, “Normalized loss functions for deep learning with noisy labels,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 6543–6553.
  * [14] Y. Wang, X. Ma, Z. Chen, Y. Luo, J. Yi, and J. Bailey, “Symmetric cross entropy for robust learning with noisy labels,” _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 322–330, 2019.
  * [15] Z. Zhang, H. Zhang, S. O. Arik, H. Lee, and T. Pfister, “Distilling effective supervision from severe label noise,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 9294–9303.
  * [16] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, “Curriculum learning,” in _ICML ’09_ , 2009.
  * [17] L. Huang, C. Zhang, and H. Zhang, “Self-adaptive training: beyond empirical risk minimization,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [18] L. Jiang, Z. Zhou, T. Leung, L. Li, and L. Fei-Fei, “Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels,” in _ICML_ , 2018.
  * [19] B. Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. Tsang, and M. Sugiyama, “Co-teaching: Robust training of deep neural networks with extremely noisy labels,” in _NeurIPS_ , 2018.
  * [20] H. Song, M. Kim, and J.-G. Lee, “Selfie: Refurbishing unclean samples for robust deep learning,” in _ICML_ , 2019.
  * [21] J. Li, R. Socher, and S. Hoi, “Dividemix: Learning with noisy labels as semi-supervised learning,” _ArXiv_ , vol. abs/2002.07394, 2020.
  * [22] S. Wang and J. Bilmes, “Robust curriculum learning: From clean la- bel detection to noisy label self-correction,” 2021.
  * [23] S. Liu, J. Niles-Weed, N. Razavian, and C. Fernandez-Granda, “Early-learning regularization prevents memorization of noisy labels,” _arXiv preprint arXiv:2007.00151_ , 2020.
  * [24] S. Reed, H. Lee, D. Anguelov, C. Szegedy, D. Erhan, and A. Rabinovich, “Training deep neural networks on noisy labels with bootstrapping,” _arXiv preprint arXiv:1412.6596_ , 2014.
  * [25] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin, “Unsupervised feature learning via non-parametric instance discrimination,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 3733–3742.
  * [26] Y. M. Asano, C. Rupprecht, and A. Vedaldi, “Self-labelling via simultaneous clustering and representation learning,” _arXiv preprint arXiv:1911.05371_ , 2019.
  * [27] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, “Unsupervised learning of visual features by contrasting cluster assignments,” _arXiv preprint arXiv:2006.09882_ , 2020.
  * [28] K.-C. Peng, T. Chen, A. Sadovnik, and A. C. Gallagher, “A mixed bag of emotions: Model, predict, and transfer emotion distributions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 860–868.
  * [29] J. Machajdik and A. Hanbury, “Affective image classification using features inspired by psychology and art theory,” in _Proceedings of the 18th ACM international conference on Multimedia_ , 2010, pp. 83–92.
  * [30] R. Panda, J. Zhang, H. Li, J.-Y. Lee, X. Lu, and A. K. Roy-Chowdhury, “Contemplating visual emotions: Understanding and overcoming dataset bias,” in _European Conference on Computer Vision_ , 2018.
  * [31] Z. Zhang and M. R. Sabuncu, “Generalized cross entropy loss for training deep neural networks with noisy labels,” _arXiv preprint arXiv:1805.07836_ , 2018\.
  * [32] L. Feng, S. Shu, Z. Lin, F. Lv, L. Li, and B. An, “Can cross entropy loss be robust to label noise,” in _Proceedings of the 29th International Joint Conferences on Artificial Intelligence_ , 2020, pp. 2206–2212.
  * [33] X. Yu, B. Han, J. Yao, G. Niu, I. Tsang, and M. Sugiyama, “How does disagreement help generalization against label corruption?” in _International Conference on Machine Learning_. PMLR, 2019, pp. 7164–7173.
  * [34] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz, “mixup: Beyond empirical risk minimization,” _arXiv preprint arXiv:1710.09412_ , 2017.
  * [35] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [36] T. Zhou, S. Wang, and J. Bilmes, “Robust curriculum learning: From clean label detection to noisy label self-correction,” in _Proceedings of the International Conference on Learning Representations, Lisbon, Portugal_ , 2021, pp. 28–29.


$\Delta_{2}={\operatorname{E}_{\operatorname{in}}}(l+s,[i+1])-{\operatorname{S}_{\operatorname{in}}}(l+s,[i+1])+{\operatorname{S}_{\operatorname{in}}}(l+r+s,[i])-1.$
(139)

A south arrival at $(l+s,[i+1])$ is the same as a south departure from
$(l+r+s,[i]),$ and an east arrival at $(l+s,[i+1])$ is the same as an east
departure from $(l,[i]),$ so

$\Delta_{2}={\operatorname{E}_{\operatorname{out}}}(l,[i])-\left({\operatorname{S}_{\operatorname{out}}}-{\operatorname{S}_{\operatorname{in}}}\right)(l+r+s,[i])-1.$
(140)

By Corollary 4.22, all edges leaving $(l,[i])$ are east edges and all edges
arriving are south edges. The same number of edges arrive and leave, so
${\operatorname{E}_{\operatorname{out}}}(l,[i])={\operatorname{S}_{\operatorname{in}}}(l,[i]).$
So,

$\Delta_{2}=({\operatorname{S}_{\operatorname{in}}}-{\operatorname{S}_{\operatorname{out}}})(l+r+s,[i])+{\operatorname{S}_{\operatorname{in}}}(l,[i])-1=\Delta_{1}.$
(141)

Substituting (141) into (137) completes the proof.∎

It remains to check that
$\operatorname{crit}_{x,c}^{+}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{-}(\lambda)$
and
$\operatorname{crit}_{x,c}^{-}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{+}(\lambda)$.

First, we make some make some straightforward but important observations about
$M_{r,s,c}(\lambda)$ and winding numbers in Proposition 6.8. Then, we apply
these to the first arrival tree to prove some formulae about distances between
consecutive vertices in the $(r,s,c)$-tour with respect to the first arrival
tree, depending on whether the vertex is eastern, southern, or a switch in
Proposition 6.9. Finally, we apply these to proving
$\operatorname{crit}_{x,c}^{+}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{-}(\lambda)$
and
$\operatorname{crit}_{x,c}^{-}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{+}(\lambda)$
in Proposition 6.10.

######  Proposition 6.8.

Let $(v,[i])$ and $(w,[j])$ be two vertices of $M_{r,s,c}(\lambda)$, and let
$p_{1}$ and $p_{2}$ be directed paths between $(v,[i])$ and $(w,[j])$. Suppose
$p_{1}$ is given by the sequence of vertices
$(v,[i])=(v_{0},[i_{0}]),\ldots,(v_{|p_{1}|,[i_{0}+|p_{1}|]})=(w,[j])$. Then,

  1. 1.

$|p_{1}|-|p_{2}|$ is divisible by $\operatorname{lcm}(c,r+s)$.

  2. 2.

Let $(v,[i])$ be $m$ lattice steps below the upper boundary of the cylinder,
and let $|p_{1}|=q\operatorname{lcm}(c,r+s)+u$ where
$-m<u\leq\operatorname{lcm}(c,r+s)-m$. The winding number of $p_{1}$ is $q$.

###### Proof.

The first point follows from Proposition 4.3: $p_{1}$ and $p_{2}$ are lattice
paths from points $(x_{1},y_{1})$ and $(x_{1}+ar,y_{1}-as)$ respectively to
points $(x_{2},y_{2})$ and $(x_{2}+br,y_{2}-bs)$ respectively, where
$\operatorname{lcm}(c,r+s)$ divides $a(r+s)$ and $b(r+s)$. We have that
$|p_{1}|=x_{2}-x_{1}+y_{1}-y_{2}$ and $|p_{2}|=x_{2}+br-x_{1}-ar+y_{1}-as-
y_{2}+bs$, so $|p_{1}|-|p_{2}|=(r+s)(a-b)$, which is divisible by
$\operatorname{lcm}(c,r+s)$.

The second point follows because as we trace out a directed path, the value of
$x-y$ moves cyclically through the residue classes modulo
$\operatorname{lcm}(c,r+s)$, incrementing by 1 with each step. ∎

######  Proposition 6.9.

Let $(k,[0])=v_{0},v_{1}\ldots,v_{(r+s)k_{1}}=(k,[0])$ be the vertices
visited, in order, by the $(r,s,c)$-tour, corresponding to the section of the
boundary of $\lambda$ between $(0,k_{1}s)$ and $(k_{1}r,0)$. Let $d_{i}$
denote the distance in the first arrival tree $T$ from $(k,[0])$ to $v_{i}$.

  1. 1.

If $v_{i}$ is a switch, or if there is a copy of the edge $(v_{i-1},v_{i})$ in
$T$, then $d_{i}-d_{i-1}=1$.

  2. 2.

If $v_{i}$ is an eastern vertex and there is no copy of $(v_{i-1},v_{i})$ in
$E(T)$, then $d_{i}-d_{i-1}=1+\operatorname{lcm}(c,r+s)$.

  3. 3.

If $v_{i}$ is a southern vertex and there is no copy of $(v_{i-1},v_{i})$ in
$E(T)$, then $d_{i}-d_{i-1}=1-\operatorname{lcm}(c,r+s)$.

###### Proof.

Write $p_{i}$ for the path in $T$ from $(k,[0])$ to $v_{i}$, so that
$|p_{i}|=d_{i}.$ The first point follows immediately from the definition of a
switch and the definition of $T$.

In general, the winding number of a vertex $v$ is the same as the winding
number of the last vertex on the upper boundary strip that $T$ before $v$. So,
drawing $T$ on the cylinder and then forgetting the identification of the two
boundary lines, the connected components form sets of vertices of equal
winding number.

Moreover, if $\operatorname{wind}(p_{i})=\operatorname{wind}(p_{i-1})$, then
by the second part of Proposition 6.8,
$||p_{i}|-|p_{i-1}||<\operatorname{lcm}(c,r+s).$ Since there is a path of
length 1 (not necessarily in $T$) connecting $v_{i-1}$ and $v_{i}$, then by
the first part of Proposition 6.8, $|p_{i}|-|p_{i-1}|\equiv
1\pmod{\operatorname{lcm}(c,r+s)}$. Therefore, $d_{i}-d_{i-1}=1,$ so $v_{i}$
is a switch or there is a copy of $(v_{i-1},v_{i})$ in $E(T)$.

For 2 and 3, we first prove that as we scan southwest along the upper boundary
strip, the winding numbers of the paths from $(k,[0])$ to the vertices on the
strip weakly increase. We proceed by induction.

$B$$A$$C$$B$$A$$A^{\prime}$$B^{\prime}$

Suppose $A$ and $B$ are vertices on the upper boundary strip and $B$ is
southwest of $A$, and let $p_{A}$ and $p_{B}$ be the paths in $T$ from
$(k,[0])$ to $A$ and $B$ respectively. We will show
$\operatorname{wind}(p_{B})\geq\operatorname{wind}(p_{A})$. If $A=(k,[0])$
then we are done, so suppose not. There is a copy of both $A$ and $B$ on the
lower boundary strip, with $B$ still southwest of $A$. Moreover, $p_{A}$ and
$p_{B}$ run from points $A^{\prime}$ and $B^{\prime}$ respectively on the
upper boundary strip to $A$ and $B$, where we possibly have
$A^{\prime}=B^{\prime}.$ However, $A^{\prime}$ cannot be strictly southwest of
$B^{\prime}$, as otherwise $p_{A}$ and $p_{B}$ would have to cross at a vertex
$C$, introducing a cycle from $(k,[0])$ following $p_{A}$ to $C$ and then
following $p_{B}$ back to $(k,[0])$. Let $p_{B}^{\prime}$ and $p_{A}^{\prime}$
be $p_{B}$ and $p_{A}$ shortened to finish at $B^{\prime}$ and $A^{\prime}$
respectively. Then, by strong induction,
$\operatorname{wind}(p_{B}^{\prime})\geq\operatorname{wind}(p_{A}^{\prime})$.
Adding 1 to both sides,
$\operatorname{wind}(p_{B})\geq\operatorname{wind}(p_{A}).$

Now, in the case that $v_{i}$ is eastern, and there is no copy of
$(v_{i-1},v_{i})$ in $E(T)$, $(v_{i-1},v_{i})$ must be a south edge, and
$v_{i-1}$ and $v_{i}$ lie in different connected components. Since
$\operatorname{wind}(p_{i})\not=\operatorname{wind}(p_{i-1}),$
$\operatorname{wind}(p_{i})>\operatorname{wind}(p_{i-1}).$ Let $D$ and $E$ be
the last vertices on the upper boundary strip on $p_{i}$ and $p_{i-1}$
respectively.

$D$$E$$v_{i-1}$$v_{i}$

Since all paths in $T$ have vertices at lattice points and do not intersect
with each other, there can be no path that starts at a vertex on the upper
boundary strip between $E$ and $D$ that crosses all the way to the lower
boundary strip. Hence, the copy of $E$ on the lower boundary strip either lies
in the same connected component as $D$ or in a component northeast of $D.$ So,
$\operatorname{wind}(p_{i})=\operatorname{wind}(p_{i-1})+1.$ Let $q_{i}$ be
the path obtained by extending $p_{i-1}$ by the south edge $(v_{i-1},v_{i})$.
Then $|q_{i}|=d_{i-1}+1.$ The second part of Proposition 6.8 tells us that
$|p_{i}|$ and $|q_{i}|$ agree modulo $\operatorname{lcm}(c,r+s)$ and therefore
$d_{i}=d_{i-1}+1+\operatorname{lcm}(c,r+s)$.

An analogous argument proves the third formula. ∎

######  Proposition 6.10.

Let $\lambda$ be a partition. Then

$\operatorname{crit}_{x,c}^{+}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{-}(\lambda)$
(142)

and

$\operatorname{crit}_{x,c}^{-}(I_{r,s,c}(\lambda))=\operatorname{crit}_{x,c}^{+}(\lambda).$
(143)

###### Proof.

We will check that
$\operatorname{crit}_{x,c}^{+}(\lambda)=(\operatorname{crit}_{x,c}^{+}+\operatorname{crit}_{x,c}^{-})(M_{r,s,c}(\lambda))-\operatorname{crit}_{x,c}^{+}(I_{r,s,c}(\lambda)).$

Recall that $\operatorname{crit}_{x,c}^{+}$ counts the total number of
inversions in the arrival word at vertices in $M_{r,s,c}(\lambda).$ Suppose
the arrival word at vertex $(v,[i])$ has $a$ south edges and $b$ east edges.
If $v$ is a switch, then $I$ reverses the arrival word at $(v,[i])$, so the
pairs of $S,E$ edges that contribute to
$\operatorname{crit}_{x,c}^{+}(I(\lambda))$ are exactly those that do not
contribute to $\operatorname{crit}_{x,c}^{+}(\lambda)$, so the contributions
over $I(\lambda)$ and $\lambda$ at $(v,[i])$ sum to $ab$.

Note that if $(v,[i])\in\operatorname{Ea}$ then $I(\lambda)$ has inversions in
the arrival word at $(v,[i])$ using the first $E$ and any $S$ in the arrival
word, and then any other pair of south and east edges contribute to
$I(\lambda)$ if and only if they do not contribute to $\lambda$, so the two
contributions sum to $ab+a.$ Similarly, if $(v,[i])\in\operatorname{So}$ then
the contributions sum to $ab-b$. Hence, we have that the total
$\operatorname{crit}_{x,c}^{+}(\lambda)+\operatorname{crit}_{x,c}^{+}(I_{r,s,c}(\lambda))$
can be written as $S_{1}+S_{2}+S_{3}$ where

$S_{1}=\sum_{(v,[i])\text{is a
switch}}{\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])$
$S_{2}=\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])+{\operatorname{S}_{\operatorname{in}}}(v,[i])$
$S_{3}=\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])-{\operatorname{E}_{\operatorname{in}}}(v,[i]).$

Now, note first that no vertex $(v,[i])$ with $v>k$ contributes to any of
these sums. Indeed, no such vertex is a switch, and the arrival word at any
such $(v,[i])$ has length $0,1$ or $2$, containing at most one $S$ and at most
one $E$. If the arrival word is empty there is nothing to prove. If the
arrival word is $E$ then the vertex is eastern, and
${\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])+{\operatorname{S}_{\operatorname{in}}}(v,[i])=0.$
If the arrival word is $S$ then the vertex is southern and
${\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])-{\operatorname{E}_{\operatorname{in}}}(v,[i])=0.$
The only other possible arrival word is $SE$, in which case the vertex is
southern and
${\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])-{\operatorname{E}_{\operatorname{in}}}(v,[i])=1-1=0.$
So, we may restrict our sum to vertices $(v,[i])$ with $v\leq k$.

Proposition 6.5 proves (122),

$(\operatorname{crit}_{x,c}^{+}+\operatorname{crit}_{x,c}^{-})(M_{r,s,c}(\lambda))=\sum_{v=0}^{k}\sum_{i=0}^{c-1}{\operatorname{E}_{\operatorname{in}}}(v,[i]){\operatorname{S}_{\operatorname{in}}}(v,[i])-\left\lfloor\frac{k_{1}(s+r)}{\operatorname{lcm}(c,r+s)}\right\rfloor.$

We wish to show that (122) is equal to $S_{1}+S_{2}+S_{3}$, and therefore it
suffices to check that

$\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i])-\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{S}_{\operatorname{in}}}(v,[i])=\left\lfloor\frac{k_{1}(s+r)}{\operatorname{lcm}(c,s+r)}\right\rfloor.$
(144)

Note that the east edges entering southern vertices and the south edges
entering eastern vertices are exactly the edges in $M_{r,s,c}(\lambda)$
arriving at non-switch vertices that are not a copy of an edge in the first
arrival tree $T$. Hence, if we let $n_{0}$ denote the number of edges $e$
entering vertices $(v,[i])$ with $v\leq k$ such that either

  * •

$(v,[i])$ is a switch, or

  * •

$(v,[i])$ is not a switch and there is a copy of $e$ in the first arrival tree
$T$,

then

$n_{0}+\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i])+\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{S}_{\operatorname{in}}}(v,[i])=k_{1}(r+s).$
(145)

Now, let $(k,[-k_{1}s])=v_{0},v_{1}\ldots,v_{(r+s)k_{1}}=(k,[k_{1}r])$ be the
vertices visited, in order, possibly with repetition, by the $(r,s,c)$-tour.
Let $d_{i}$ denote the distance in the first arrival tree from $(k,[-k_{1}s])$
to $v_{i}$. Now $c\mid k_{1}$ by assumption, and thus $c\mid(r+s)k_{1}$, so we
have that

$0=d_{(r+s)k_{1}}=\sum_{i=1}^{(r+s)k_{1}}d_{i}-d_{i-1}.$ (146)

Substituting the formulae for $d_{i}-d_{i-1}$ proven in Proposition 6.9 into
(146) and writing $l$ for $\operatorname{lcm}(c,r+s)$,

$n_{0}+(1+l)\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{S}_{\operatorname{in}}}(v,[i])+(1-l)\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i])=0.$
(147)

Subtracting (147) from (145) gives

$k_{1}(r+s)=\operatorname{lcm}(c,r+s)\left(\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i])-\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{S}_{\operatorname{in}}}(v,[i])\right).$
(148)

Now, since $k$ is divisible by $rsc$, $k_{1}=\frac{k}{rs}$ is divisible by
$c$, so $\operatorname{lcm}(c,r+s)$ divides $k_{1}(r+s)$. Therefore,

$\left\lfloor\frac{k_{1}(r+s)}{\operatorname{lcm}(c,r+s)}\right\rfloor=\frac{k_{1}(r+s)}{\operatorname{lcm}(c,r+s)}=\sum_{(v,[i])\in\operatorname{So}}{\operatorname{E}_{\operatorname{in}}}(v,[i])-\sum_{(v,[i])\in\operatorname{Ea}}{\operatorname{S}_{\operatorname{in}}}(v,[i])),$

which is (144), which completes the proof. ∎

###  6.3 Extended Example

Let $c=2$ and $n=7$, and $\mu=(2,1).$ Then

$\operatorname{Par}^{2}_{\mu}(7)=\\{(6,1),(4,3),(4,1,1,1),(2,2,2,1),(2,1,1,1,1,1)\\}.$
(149)

Figure 15: the partitions in $\operatorname{Par}^{2}_{\mu}(7)$ with boxes of
even hook length coloured yellow.

For the shaded cells, the set of values of $\frac{a(\square)}{l(\square)+1}$
is $\left\\{3,1,0,\frac{1}{3}\right\\},$ and the set of values of
$\frac{a(\square)+1}{l(\square)}$ is
$\left\\{\infty,3,1,\frac{1}{3}\right\\}$. So, the critical rationals are
$\left\\{0,\frac{1}{3},1,3,\infty\right\\}.$

In this example, we will verify that

$\sum_{\lambda\in\operatorname{Par}^{2}_{\mu}(7)}t^{h_{4,2}^{+}(\lambda)}=\sum_{\operatorname{Par}^{2}_{\mu}(7)}t^{\lambda^{2*}_{\square}}.$

Recall

$h_{4,2}^{+}(\lambda)=\left|\left\\{\square\in\lambda:2\mid h(\square)\text{
and }\frac{a(\square)}{l(\square)+1}\leq
4<\frac{a(\square)+1}{l(\square)}\right\\}\right|.$ (150)

From our computation of the critical rationals, given that $2\mid h(\square)$
for some box in a partition $\lambda\in\operatorname{Par}^{2}_{\mu}(7),$
$4<\frac{a(\square)+1}{l(\square)}$ if and only if
$3<\frac{a(\square)+1}{l(\square)}$, and $\frac{a(\square)}{l(\square)+1}\leq
4$ if and only if $\frac{a(\square)}{l(\square)+1}\leq 3.$ So,
$h_{4,2}^{+}(\lambda)=h_{3,2}^{+}(\lambda)$. Now we use
$I_{3,1,2}:\operatorname{Par}^{2}_{\mu}(7)\to\operatorname{Par}^{2}_{\mu}(7)$.
Because
$\operatorname{mid}_{3,2}(\lambda)=\operatorname{mid}_{3,2}(I_{3,1,2}(\lambda))$
and
$\operatorname{crit}^{\pm}_{3,2}(\lambda)=\operatorname{crit}^{\mp}_{3,2}(\lambda)$,
$I_{3,1,2}$ is a bijection exchanging $h_{3,2}^{+}$ and $h_{3,2}^{-},$ so

$\sum_{\lambda\in\operatorname{Par}^{2}_{\mu}(7)}t^{h_{3,2}^{+}(\lambda)}=\sum_{\lambda\in\operatorname{Par}^{2}_{\mu}(7)}t^{h_{3,2}^{-}(\lambda)}.$

We now explicitly compute $I_{3,1,2}(\lambda)$ for $\lambda=(6,1).$

The diagram of $(6,1)$ lies below the line $3y+x=9.$ So, we choose the
smallest value $k\geq 9$ such that $3\times 2\times 1\mid k,$ $k=12.$ Then,
$k_{1}=\frac{12}{3}=4.$

The $(r,s,c)$-tour of $M_{3,1,2}((6,1))$ is defined by the following family of
arrival words.

(4,[0]) | S | (5,[1]) | E | (6,[0]) | SSE
---|---|---|---|---|---
(7,[1]) | EEE | (8,[0]) | E | (9,[1]) | SEE

and for $w>9,$

$(w,[i])_{a}=\begin{cases}SE&3\mid w,w\equiv\frac{-w}{3}\equiv i\pmod{2}\\\
E&2\mid\left(w-i\right)\text{ and either }3\nmid w\text{ or
}2\nmid(\frac{-w}{3}-i)\\\ S&3\mid
w,2\mid\left(\frac{-w}{3}-i\right),2\nmid(w-i)\\\
\text{empty}&\text{otherwise}\\\ \end{cases}.$ (151)

The multigraph is given in Figure 16 with the edges in the first arrival tree
in bold.

$\vdots$(12,[0])(9,[1])(6,[0])(7,[1])(4,[0])(4,[0])(5,[1])(8,[0])(8,[0])(10,[0])(11,[1])(12,[0])
Figure 16: $M_{3,1,2}((6,1))$ with the edges of the first arrival tree in
bold.

After applying $I_{3,1,2}$ the arrival words are

(4,[0]) | S | (5,[1]) | E | (6,[0]) | SSE
---|---|---|---|---|---
(7,[1]) | EEE | (8,[0]) | EE | (9,[1]) | SEE

with all arrival words at $(w,[i])$ with $w>9$ unchanged. These arrival words
correspond to the partition $(4,3).$ So,
$h_{3,2}^{+}((6,1))=h_{3,2}^{-}((4,3)).$

From our computation of the critical rationals, given that $2\mid h(\square)$
for some box in a partition $\lambda\in\operatorname{Par}^{2}_{\mu}(7),$
$3\leq\frac{a(\square)+1}{l(\square)}$ if and only if
$1<\frac{a(\square)+1}{l(\square)}$, and $\frac{a(\square)}{l(\square)+1}<3$
if and only if $\frac{a(\square)}{l(\square)+1}\leq 1.$ So,
$h_{3,2}^{-}(\lambda)=h_{1,2}^{+}(\lambda)$ for all
$\lambda\in\operatorname{Par}^{2}_{\mu}(7)$. Now, $I_{1,1,2}$ exchanges
$h_{1,2}^{+}$ and $h_{1,2}^{-}$, and $I_{1,1,2}((4,3))=(2,2,2,1)$, so
$h_{4,2}^{+}((6,1))=h_{1,2}^{+}((2,2,2,1)).$ Using the same logic again
$h_{1,2}^{+}(\lambda)=h_{\frac{1}{3},2}^{-}(\lambda)$ for each
$\lambda\in\operatorname{Par}^{2}_{\mu}(7).$ Using $I_{1,3,2}$,
$I_{1,3,2}((2,2,2,1))=(2,1,1,1,1,1),$ so
$h_{4,2}^{+}((6,1))=h_{\frac{1}{3},2}^{-}((2,1,1,1,1,1))$. Finally, for any
partition $\lambda\in\operatorname{Par}^{2}_{\mu}(7),$
$\frac{1}{3}\leq\frac{a(\square)+1}{l(\square)}$ if and only if
$0<\frac{a(\square)+1}{l(\square)}$, and
$\frac{a(\square)}{l(\square)+1}<\frac{1}{3}$ if and only if $a(\square)=0,$
if and only if $\frac{a(\square)}{l(\square)+1}\leq 0,$ so
$h^{-}_{\frac{1}{3},2}(\lambda)=h^{+}_{0,2}(\lambda).$

Therefore, since

$I_{1,3,2}\circ I_{1,1,2}\circ I_{3,1,2}((6,1))=(2,1,1,1,1,1),$

we have that $h^{+}_{4,2}(6,1)=h^{+}_{0,2}(2,1,1,1,1,1).$ For the other
partitions in $\operatorname{Par}^{2}_{\mu}(7),$

$I_{1,3,2}\circ I_{1,1,2}\circ I_{3,1,2}(4,3)=I_{1,3,2}\circ
I_{1,1,2}((6,1))=I_{1,3,2}(2,1,1,1,1,1)=(2,2,2,1),$ $I_{1,3,2}\circ
I_{1,1,2}\circ I_{3,1,2}(4,1,1,1)=I_{1,3,2}\circ
I_{1,1,2}((4,1,1,1))=I_{1,3,2}(4,1,1,1)=(4,1,1,1).$ $I_{1,3,2}\circ
I_{1,1,2}\circ I_{3,1,2}(2,2,2,1)=I_{1,3,2}\circ
I_{1,1,2}((2,2,2,1))=I_{1,3,2}(4,3)=(4,3).$ $I_{1,3,2}\circ I_{1,1,2}\circ
I_{3,1,2}(2,1,1,1,1,1)=I_{1,3,2}\circ
I_{1,1,2}((2,1,1,1,1,1))=I_{1,3,2}(6,1)=(6,1).$

Hence we can verify the equidistribution of $h^{+}_{x,2}$ with $h^{-}_{x,2}$
over $\operatorname{Par}_{\mu}^{2}(7)$ for each $x\in\mathbb{R}_{>0},$ thus
verifying Theorem 3.3 in this case.

##  7 Further Work

We note here that Problem 8.9 in [9] may be amenable to similar techniques.

### Acknowledgements

The author is indebted to her PhD supervisor Paul Johnson for suggesting the
problem and for many helpful conversations. The author is funded by an EPSRC
studentship333UKRI grant number EP/R513313/1..

## References

  * [1] T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin, 28: 203–217, 1951.
  * [2] A. Białynicki-Birula, Some properties of the decompositions of algebraic varieties determined by actions of a torus, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 24(9): 667–674, 1976.
  * [3] Alexandr Buryak, Boris Lvovich Feigin, and Hiraku Nakajima, A simple proof of the formula for the Betti numbers of the quasihomogeneous Hilbert schemes, Int. Math. Res. Not. IMRN, 13: 4708–4715, 2015.
  * [4] G.D. James, Some combinatorial results involving Young diagrams, Math. Proc. Cambridge Philos. Soc., 83(1):1–10, 1978.
  * [5] Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, xxviii+510, Addison-Wesley, 1981\.
  * [6] D.E. Littlewood, Modular representations of symmetric groups, Proc. Roy. Soc. London Ser. A, 209, 333–353, 1951.
  * [7] Nicholas A. Loehr and Gregory S. Warrington, A continuous family of partition statistics equidistributed with length, J. Combin. Theory Ser. A, 116(2): 379–403, 2009.
  * [8] Tadasi Nakayama, On some modular properties of irreducible representations of symmetric groups. II, Jpn. J. Math., 17, 411–423, 1941.
  * [9] Adam Walsh and S. Ole Warnaar, Modular Nekrasov-Okounkov formulas, Sém. Lothar. Combin., 81, Art. B81c, 28, 2020.