#  ExpertNet: A Symbiosis of Classification and Clustering

Shivin Srivastava1 Kenji Kawaguchi1 &Vaibhav Rajan1 1 National University of
Singapore
{shivin, kenji<EMAIL_ADDRESS>
###### Abstract

A widely used paradigm to improve the generalization performance of high-
capacity neural models is through the addition of auxiliary unsupervised tasks
during supervised training. Tasks such as similarity matching and input
reconstruction have been shown to provide a beneficial regularizing effect by
guiding representation learning. Real data often has complex underlying
structures and may be composed of heterogeneous subpopulations that are not
learned well with current approaches. In this work, we design ExpertNet, which
uses novel training strategies to learn clustered latent representations and
leverage them by effectively combining cluster-specific classifiers. We
theoretically analyze the effect of clustering on its generalization gap, and
empirically show that clustered latent representations from ExpertNet lead to
disentangling the intrinsic structure and improvement in classification
performance. ExpertNet also meets an important real-world need where
classifiers need to be tailored for distinct subpopulations, such as in
clinical risk models. We demonstrate the superiority of ExpertNet over state-
of-the-art methods on $6$ large clinical datasets, where our approach leads to
valuable insights on group-specific risks.

##  1 Introduction

Overfitting is a common problem in high-capacity models, such as neural
networks, that adversely affects generalization performance. A standard
approach to reduce overfitting is regularization. Various regularization
strategies have been developed such as those based on norm penalties and some
specifically designed for neural networks such as dropout and early stopping
Goodfellow et al. (2016). The use of auxiliary tasks have also been explored
for regularization. The rationale comes from multi-task learning, which is
known to improve generalization through improved statistical strength via
shared parameters Baxter (1995); Caruana (1997).

Since there is no dependence on label acquisition, several unsupervised
auxiliary tasks have been explored for regularizing neural networks. Input
reconstruction is a common choice, often implemented using autoencoder-like
architectures, e.g. Rasmus et. al. (2015); Zhao (2015); Zhang et al. (2016);
Le et al. (2018). Such reconstruction-based regularization has the advantage
of yielding hidden layer representations closer to the original data topology.

Real data, however, contains complex underlying structures like clusters and
intrinsic manifolds that are not disentangled by the bottleneck layer of
autoencoders. This has been studied in the context of purely unsupervised
models that have explored the joint tasks of clustering and dimensionality
reduction (DR) to find “cluster-friendly” representations. E.g., in Yang
(2017), it is shown that joint clustering and DR outperforms the disassociated
approach of independently performing DR followed by clustering. Recognizing
the importance of preserving cluster structure in latent embedded spaces, we
hypothesize that, in addition to reconstruction, clustering-based
regularization could improve generalization performance in supervised models.

Our work is also motivated by the need to develop models tailored to distinct
subpopulations in the data. This is a common requirement in clinical risk
models since patient populations can show significant heterogeneity. Most
previous works adopt a ‘cluster-then-predict’ approach to model such data
e.g., Ibrahim et. al. (2020), where clustering is first done independently to
find subpopulations (called subtypes) and then predictive models for each of
these clusters are learnt. Such subtype-specific models are often found to
outperform models learnt from the entire population Masoudnia and Ebrahimpour
(2014). They also provide a form of interpretability and subsequent clinical
decisions can be personalized to each patient group’s characteristics.
However, in these approaches, clustering is performed independent of
classifier training, and may not discover latent structures that are
beneficial for subsequent classification. This leads us to hypothesize that
combined clustering with supervised classification will lead to better
performance compared to such cluster-then-predict approaches.

We thus design ExpertNet, a deep learning model that performs simultaneous
clustering and classification. ExpertNet consists of components that have both
local and global view of the data space. The local units specialize in
classifying observations in clusters found in the data while the global unit
is responsible for generating cluster friendly embeddings based on the
feedback given by local units. Apart from being a supervised model, ExpertNet
can function as an unsupervised model that can perform target-specific
clustering. In summary, our contributions are:

  1. 1.

Model: We design ExpertNet, a neural model for simultaneous clustering and
classification with cluster-specific local networks. We introduce novel
training strategies to obtain latent clusters and use them effectively to
improve generalization of the classifiers.

  2. 2.

Theoretical Guarantees: We analyze the effect of clustering on ExpertNet’s
generalization gap.

  3. 3.

Experiments: Our extensive experiments demonstrate the efficacy of our model
over both reconstruction-based regularization and cluster-then-predict
approaches. On $6$ large real-world clinical datasets ExpertNet achieves
clustering performance that is comparable to, and achieves classification
performance that is considerably better than, state-of-the-art methods.

##  2 Background and Related Work

Unsupervised learning techniques are often used to pretrain a neural network
before finetuning with supervised tasks Bengio et al. (2007). Input
reconstruction is commonly used to regularize deep models. Zhang et al. (2016)
jointly train a supervised neural model with an unsupervised reconstruction
network. Zhao (2015) showed that by adding decoding pathways, to add an
auxiliary reconstruction task to the objective, improves the performance of
supervised networks. Similarly Le et al. (2018) append a prediction layer to
the embedding layer to improve generalization performance.

A more dissociated way of using clustering to benefit supervised models is to
simply find clusters in the data and then train separate models on each of
them that. Amongst such techniques, there are some algorithms Finley and
Joachims (2008); Gu and Han (2013); Fu et al. (2010) that impose a common,
global regularization scheme on all the individual classifiers. In some other
works Reyna et. al. (2019); Lasko et al. (2013); Suresh et al. (2018), all the
individual classifiers are completely independent. Such analysis is common in
clinical data where patient stratification is done followed by predictive
modeling. E.g., Deep Mixture Neural Networks (DMNN) Li et al. (2020b),
designed with this aim, is based on an autoencoder architecture while having
an additional gating network, which is first trained to learn clusters through
$k$-means. Local networks corresponding to each cluster are trained using a
weighted combination of losses, where the weights are determined by the gates.

Simultaneous clustering and representation learning have been used in purely
unsupervised settings. Examples include neural clustering models such as Deep
Embedded Clustering (DEC) Xie et al. (2016) and Improved DEC (IDEC) Guo et al.
(2017) and Deep Clustering Network (DCN) Yang (2017). Recent self-supervised
learning techniques also employ cluster centroids as pseudo class labels in
embedded data space to improve the quality of representations Li et al.
(2020a); Caron et al. (2018).

We briefly describe DEC Xie et al. (2016) as the loss function in ExpertNet is
based on their formulation. Their key idea is to find latent representations
$z_{i}$ for data points using an autoencoder by first pretraining it. Initial
cluster centers $\\{\mu_{j}\\}$ are obtained by using $k$-means on the latent
representations. The decoder is then removed and the representations are fine
tuned by minimizing the loss function:

$\displaystyle
L_{c}=KL(P||Q)=\sum_{i=1}^{N}\sum_{j=1}^{N}p_{ij}\log\frac{p_{ij}}{q_{ij}}$
(1)

where $q_{ij}$ is the probability of assigning the $i^{\rm th}$ data point
($z_{i}$) to the $j^{\rm th}$ cluster (with centroid $\mu_{j}$) measured by
the Student’s $t$-distribution V. D. Maaten and Hinton (2008) as:

$\displaystyle
q_{ij}=\frac{(1+\|z_{i}-\mu_{j}\|^{2})^{-1}}{\sum_{j}(1+\|z_{i}-\mu_{j}\|^{2})^{-1}}$
(2)

The target distribution $p_{ij}$ is defined as

$\displaystyle
p_{ij}=\frac{\nicefrac{{q_{ij}^{2}}}{{\sum_{i}q_{ij}}}}{\sum_{j}(\nicefrac{{q_{ij}^{2}}}{{\sum_{i}q_{ij}}})}$
(3)

The predicted label of $x_{i}$ is $\mathop{\mathrm{argmax}}_{j}q_{ij}$.
Minimizing the loss function $L_{c}$ is a form of self-training as points with
high confidence act as anchors and distribute other points around them more
densely.

DEC, IDEC and DCN are all centroid-based and have objectives similar to that
of $k$-means. In such approaches, the encoder can map the centroids to a
single point to make the loss zero and thus collapse the clusters. Hence,
previous methods employ various heuristics to balance cluster sizes, e.g.,
through sampling approaches Caron et al. (2018) or use of priors Jitta and
Klami (2018).

##  3 ExpertNet

Given $N$ datapoints $\\{x_{i}\in X\\}^{N}_{i=1}$, and class labels
$y_{i}\in\\{1,\dots,\mathcal{B}\\}$, associated with every point $x_{i}$, our
aim is to simultaneously (i) cluster the $N$ datapoints into $k$ clusters,
each represented by a centroid $\mu_{j},j\in\\{1,\dots,k\\}$, and (ii) build
$k$ distinct supervised classification models within each cluster to predict
the class labels. Note that during training, labels are used only for building
the classification models and not for clustering.

####  3.0.1 Network Architecture

Fig. 1 shows the neural architecture of ExpertNet that consists of an encoder,
a decoder and $k$ local networks ($LN_{j}$). The encoder
$f(\mathcal{U}):X\xrightarrow{}Z$ is used to obtain low-dimensional
representations of the input datapoints. Cluster structure is learnt in this
latent space and representations in each cluster are used in local networks,
$h(\mathcal{W}_{j}):Z\xrightarrow{}\hat{y}_{j}$ for $j=1\ldots k$ to train $k$
classification models. In addition, there is a decoder
$g(\mathcal{V}):Z\xrightarrow{}X$ that is used to reconstruct the input from
the embeddings. ExpertNet is parameterized by three sets of weights:
$\mathcal{U},\mathcal{V},\\{\mathcal{W}_{j}\\}_{j=1}^{k}$ which are learnt by
optimizing a combination of losses as described below.

Figure 1: ExpertNet Architecture

####  3.0.2 Loss Function

The overall loss function $L$ is a weighted combination, with coefficients
$\beta,\gamma>0$, of the reconstruction loss $L_{r}$, clustering loss $L_{c}$,
cluster balance loss $L_{bal}$ and classification loss $L_{s}$:

$\displaystyle L=L_{r}+\beta\cdot L_{c}+\gamma\cdot L_{s}+\delta\cdot L_{bal}$
(4)

$L_{c}$ is defined as the KL divergence loss (Eq. 1), where the cluster
membership distribution $Q$ (Eq. 2) uses representations $z_{i}$ and cluster
centroids $\mu_{j}$ inferred during ExpertNet training. As suggested in Guo et
al. (2017); Yang (2017), to prevent distortion in the latent space and improve
clustering performance, we add the reconstruction loss measured by mean
squared error:

$L_{r}=\sum_{i=1}^{N}\|x_{i}-g(f(x_{i}))\|^{2}$ (5)

We design a novel cluster balance loss to discourage unevenly distributed
cluster sizes. We define the ‘soft’ size of a cluster $C_{j}$ as
$|C_{j}|=\sum_{i}q_{ij}$ and cluster support counts
$\mathbf{S}=[|C_{1}|,|C_{2}|,\dots,|C_{k}|]$ as a $k$-dimensional probability
distribution. Let $\mathbf{U_{k}}=(\nicefrac{{1}}{{k}})\mathbf{U}(0,1)$ denote
the $k$-dimensional uniform distribution function. We use the Hellinger
distance ($H$), which measures the dissimilarity between two distributions, as
the loss
${L_{bal}=H(\mathbf{S}||\mathbf{U_{k}})=\frac{1}{2}\|\sqrt{S}-\sqrt{U_{k}}\|_{2}}.$
$L_{s}$ is a weighted cross entropy loss described in the following.

####  3.0.3 ExpertNet Training

To initialize the parameters $(\mathcal{U},\mathcal{V})$, we first pre-train
the encoder and decoder with the input data using only the reconstruction loss
$L_{r}$. This is followed by $k$-means clustering on
$\\{z_{i}=f(x_{i};\mathcal{U})\\}^{N}_{i=1}$ to obtain cluster centroids
$\\{\mu_{i}\\}_{i=1}^{k}$ which are used to calculate cluster membership and
target distributions, $Q,P$. After initialization, we use mini-batch
Stochastic Gradient Descent to train the entire network, using the loss $L$
(details are in Appendix E). To stabilize training we update $P$ only after
every epoch.

Input: Training Data: $X\in\mathbb{R}^{n\times d}$, labels $y^{n\times
1}\in[\mathcal{B}]^{n}$, $k$, $f(\cdot;\mathcal{U}),g(\cdot;\mathcal{V})$ and
$\\{h_{j}(\cdot;\mathcal{W}_{j})\\}_{j=1}^{k}$, $\mathcal{J}$

1 $\triangleright$ Initialization

2 Pre-train $f(\cdot;\mathcal{U})$ & $g(\cdot;\mathcal{V})$ via back-
propagating loss in eq. 5

3 Compute $\mu(C_{j})\forall\ C_{j}\ s.t.\ j\in[k]$ and $b\in[\mathcal{B}]$

4 Compute matrices $Q$ and $P$ according to eqs. 2 and 3

5$\triangleright$ Algorithm

6 while  _Validation AUC increases_ do

7 for  _every mini-batch $\mathcal{X}_{b}$_ do

8 $\mathcal{Z}_{b}\xleftarrow{}f(\mathcal{X}_{b};\mathcal{U})$

9 Calculate $Q_{b}$ by eq. (2)

10 for  _$T$ sub-iterations_ do

11 Sample $\\{s_{i}\sim q_{i\cdot}\\}_{i=1}^{|\mathcal{X}_{b}|}$

12 Calculate
$\\{\mathcal{X}_{m}=\\{x_{i}:s_{i}=j\\}_{i=1}^{|\mathcal{X}_{b}|}\\}_{j=1}^{k}$

13 Train local classifiers $\\{h_{j}\\}_{j=1}^{k}$ on
$(\mathcal{X}_{j},\mathcal{Y}_{j})$

14 Update $\\{\mathcal{W}_{j}\\}_{j=1}^{k}$

15 Backpropagate $L=L_{r}+\beta\cdot L_{c}+\gamma\cdot L_{s}+\delta\cdot
L_{bal}$ and update $\mu,\mathcal{U},\mathcal{V}$ and $\mathcal{W}$

16 Update $P$ via eq. (3)

17$\triangleright$ Fine tune Local Classifiers

18 For every cluster $C_{j}$, train a classifier $f_{j}$ on
$(\mathcal{X}_{j},\mathcal{Y}_{j})$.

Output Trained ExpertNet model. Cluster centroids
$\mu=\\{\mu_{j}\\}_{j=1}^{k}$

Algorithm 1 ExpertNet Training

Since the embeddings get updated progressively in every iteration, we train
the LNs for a larger number of sub-iterations within every iteration of the
main training loop. The number of sub-iterations gradually increases ($1$ per
every 5 epochs until a max-limit we set to $10$). This enables the LNs to
learn better from the stabilized clustered embeddings than from the
intermediate representations.

Further, we design a novel strategy called stochastic cohort sampling used in
each sub-iteration, which leads to more robust classifiers, as verified in our
experiments. Instead of training each LN with a fixed cluster of data points
(e.g., using $\mathop{\mathrm{argmax}}_{j=1}^{k}q_{i,j}$), we leverage the
probabilistic definition of clusters to obtain multiple, different cluster
assignments for the same set of embeddings. Considering $q_{i\cdot}$, the
$i^{th}$ row of $Q$, as a cluster probability distribution for $z_{i}$, we
sample a random variable $s_{i}$ from $q_{i\cdot}$, denoting the cluster
assignment for the point $x_{i}$. We can define a cluster realization
$C_{m}=\\{i:s_{i}=m\\}_{i=1}^{N}$ (i.e. index of all the points assigned to
cluster $C_{m}$) and $\mathcal{X}_{m}=\bigcup\limits_{j\in C_{m}}\\{x_{j}\\}$.
The LNs are trained on these cluster realizations for $T-1$ sub-iterations
without backpropagating the error to the encoder. The individual errors are
collected from all the $k$ LNs only at the last ($T^{\rm th}$) iteration and
backpropagated to the encoder to adjust the cluster representations
accordingly. The final classification loss is a weighted cross entropy (CE)
loss:

$L_{s}=\sum_{j=1}^{k}\sum_{p\in
C_{j}}q_{p,j}\operatorname{CE}(y_{p},h_{j}(x_{p};\mathcal{V}_{j})).$ (6)

After training, the encoder network is frozen and the local networks are
finetuned on the latent embeddings via stochastic cohort sampling to further
improve LN performance.

####  3.0.4 ExpertNet Prediction

Prediction can be done using the encoder and local networks. For a test point
$\hat{x}_{p}$, the soft cluster probabilities ($\hat{q}_{pj}$) are calculated
from Eq. 2. All the local networks (see stochastic cohort sampling above) can
be used to predict the class label
$\hat{y}_{p}=\sum_{j=1}^{k}\hat{q}_{pj}h_{j}(\hat{x}_{p})$.

##  4 Theoretical Analysis

Let $\\{\Omega_{j}\\}_{j=1}^{k}$ be a partition of $\mathcal{X}$ such that
$\mathcal{X}=\cup_{j=1}^{k}\Omega_{j}$ where
$\Omega_{j}\cap\Omega_{j^{\prime}}=\emptyset$ for $j\neq j^{\prime}$. This
corresponds to the inverse image of clustering at the space of $z$. We define
$N_{j}$ as

$N_{j}=\sum_{i=1}^{N}\mathbbm{1}\\{x_{i}\in\Omega_{j}\\};f(x)=\sum_{j=1}^{k}\mathbbm{1}\\{x\in\Omega_{j}\\}f_{j}(x)$

where $f_{j}=g_{j}\circ f$ with $g_{j}$ being the encoder for the cluster
$\Omega_{j}$ and $f$ being the shared encoder.

While we provide the results for multi-class classification in Appendix A,
this section considers binary classification. For binary classification
problems with $y\in\\{-1,+1\\}$ and $f(x)\in\mathbb{R}$, define the margin
loss as follows:

${\ell}_{\rho}(f(x),y)={\ell}_{\rho}^{(1)}(f(x)y)$

where

${\ell}_{\rho}^{(1)}(q)=\begin{cases}0&\text{if }\rho\leq q\\\
1-q/\rho&\text{if }0\leq q\leq\rho\\\ 1&\text{if }q\leq 0.\\\ \end{cases}$

Define the 0-1 loss as:

$\textstyle\ell_{01}(f(x),y)=\mathbbm{1}\\{f(x)y\leq 0\\}.$

To simplify the equation and discussion, we consider the case where
$\Pr(x\in\Omega_{j})=1/k$ (uniform) and $N_{j}=N/k$ (uniform), whereas the
results for a more general case are presented in the appendix. Defining
$\hat{\mathbb{E}}_{x,y}[\ell_{\rho}(f(x),y)]$ to denote the empirical los, we
have:

######  Theorem 1.

Suppose that for all $j\in\\{0,\dots,k\\}$, the function $\sigma_{l}^{j}$ is
1-Lipschitz and positive homogeneous for all $l\in[\max(L-1,Q-1)]$ and
$\|x^{j}\|\leq B_{j}$ for all $x^{j}\in\Omega_{j}$. Let
$\mathcal{F}_{j}=\\{x\in\Omega_{j}\mapsto(g_{j}\circ e)(x):(\forall
l\in[L-1])[\|W_{l}^{j}\|_{F}\leq M_{l}^{j}\wedge\|W_{l}^{0}\|_{F}\leq
M_{l}^{0}]\\}$ and $\mathcal{F}^{k}=\\{x\mapsto
f(x):f(x)=\sum_{j=1}^{k}\mathbbm{1}\\{x\in\Omega_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$.
Then, for any $\delta>0$, with probability at least $1-\delta$ over an i.i.d.
draw of $m$ i.i.d. test samples $((x_{i},y_{i}))_{i=1}^{m}$, the following
holds: for all maps $f^{k}\in\mathcal{F}^{k}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f^{k}(x),y)]$
$\displaystyle-\hat{\mathbb{E}}_{x,y}[\ell_{\rho}(f^{k}(x),y)]\leq$
$\displaystyle\frac{\zeta_{1}\left(\sum_{j=1}^{K}B_{j}\prod_{l=1}^{L}M_{l}^{j}\right)}{\sqrt{kN}}$
$\displaystyle+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}$

where $\zeta_{1}=2\rho^{-1}(\sqrt{2\log(2)(L+Q)}+1)(\prod_{l=1}^{Q}M_{l}^{0})$
is a $k$ independent term.

The proof is presented in Appendix A. Theorem 1 shows the generalization bound
with the following:

  * •

Increasing $k$ can reduce the empirical loss
$\mathbb{E}_{x,y}[\ell_{\rho}(f^{k}(x),y)]$ (since it increases the expressive
power), resulting in a tendency for a better expected error
$\mathbb{E}_{x,y}[\ell_{01}(f^{k}(x),y)]$.

  * •

Increasing $k$ increases the last term $\sqrt{\frac{k\ln(2k/\delta)}{2N}}$ ,
resulting in a tendency for a worse expected error
$\mathbb{E}_{x,y}[\ell_{01}(f^{k}(x),y)]$.

  * •

Increasing $k$ can reduce the complexity term
$\frac{\left(\sum_{j=1}^{k}B_{j}\prod_{l=1}^{L}M_{l}^{j}\right)}{\sqrt{kN}}$
(since (1) each sub-network only needs to learn a simpler classifier with
larger $k$, resulting in a smaller value of $\prod_{l=1}^{L}M_{l}^{j}$; (2)
each domain decrease and hence $B_{j}$ decrease as $k$ increase), resulting in
a tendency for a better expected error
$\mathbb{E}_{x,y}[\ell_{01}(f^{k}(x),y)]$.

Not surprisingly, the generalization gap is inversely dependent on $N$, the
total number of data points, indicating that more observations will lead to a
more accurate model. There is no simple relationship between $k$ suggesting
that the best number of clusters might have to be found empirically.

(a) F1/AUC vs. $\beta$

(b) F1/AUC vs. $\gamma$

(c) F1/AUC vs. $\delta$

(d) F1

(e) AUC

(f) HTFD

Figure 2: Sensitivity Analysis (a–c) and Ablation Studies (d–f) on the CIC
dataset

##  5 Experiments

We evaluate the classification and clustering performance of ExpertNet on 6
large clinical datasets. We analyze ExpertNet through an ablation study and
investigate its sensitivity to model hyperparameters. Finally, we present a
case study that illustrates its utility in clinical risk modeling.

###  5.1 Data

We use 6 large clinical datasets; Table 1 lists the number of observations and
features in each of them. WID data is from the Women In Data Science challenge
Lee et. al. (2020) to predict patient mortality. Diabetes data is from the UCI
Repository where the task is readmission prediction. All the remaining
datasets have data from the MIMIC III ICU Database Fei et al. (2020). CIC and
Sepsis have been used for mortality and sepsis prediction challenges in
Physionet Silva (2012); Reyna et. al. (2019). Kidney and Respiratory data has
been extracted by us for the tasks of Acute Kidney Failure and Acute
Respiratory Distress Syndrome prediction. All the above tasks are posed as
binary classification problems. We also derive a multiclass dataset (CIC-LOS)
from the CIC dataset where we predict Length of Stay (LOS), discretized into 3
classes (based on 3 quartiles). We consider a random 57-18-25 split to create
training, validation and testing splits in each dataset. More details of data
preprocessing and feature extraction are in Appendix D.

Dataset #Instances #Features MAJ WID Mortality Lee et. al. (2020) $91711$
$241$ $0.91$ Diabetes Lichman. (2013) $100000$ $9$ $0.54$ Sepsis Reyna et. al.
(2019) $40328$ $89$ $0.93$ Kidney Fei et al. (2020) $14087$ $89$ $0.51$
Respiratory Fei et al. (2020) $22477$ $89$ $0.92$ CIC Silva (2012) $12000$
$117$ $0.85$ CIC-LOS $12000$ $116$ 3 classes

Table 1: Summary of datasets. MAJ: proportion of majority class instances (for
binary labels).

HTFD AUC Dataset k KMeans DCN IDEC DMNN ExpertNet Baseline SAE KMeans-Z DCN-Z
IDEC-Z DMNN ExpertNet CIC 1 - - - - - $0.628$ $0.693$ $0.804$ $0.819$ $0.817$
$0.721$ $\mathbf{0.835}$ 2 $1.125$ NA ${1.175}$ $1.233$ $\mathbf{1.302}$
$0.705$ NA $0.787$ $0.784$ $\mathbf{0.851}$ 3 $1.072$ NA $1.081$
$\mathbf{1.173}$ $\mathbf{1.082}$ $0.63$ NA $0.817$ $0.799$ $\mathbf{0.853}$ 4
$0.992$ NA $0.971$ $\mathbf{1.107}$ $0.934$ $0.593$ NA $0.811$ $0.808$
$\mathbf{0.837}$ Sepsis 1 - - - - - $0.654$ $0.681$ $0.823$ $0.772$ $0.823$
$0.670$ $\mathbf{0.908}$ 2 $1.347$ $1.365$ $1.406$ $\mathbf{1.476}$ $1.283$
$0.598$ $0.679$ $0.806$ $0.767$ $\mathbf{0.909}$ 3 $\mathbf{1.455}$ $1.376$
$1.301$ $1.351$ $1.319$ $0.58$ $0.725$ $0.772$ $0.794$ $\mathbf{0.899}$ 4
${1.357}$ NA $\mathbf{1.361}$ $1.333$ $1.301$ $0.55$ NA $0.804$ $0.829$
$\mathbf{0.904}$ AKI 1 - - - - - $0.584$ $0.552$ $0.601$ $0.591$ $0.613$
$0.617$ $\mathbf{0.694}$ 2 ${1.108}$ $1.014$ $\mathbf{1.11}$ $0.760$ $1.044$
$0.44$ $0.601$ $0.585$ $0.690$ $\mathbf{0.69}$ 3 $1.164$ $1.166$ $1.166$
$0.803$ $\mathbf{1.168}$ $0.467$ $0.582$ $0.57$ $\mathbf{0.689}$ ${0.67}$ 4
$1.148$ $1.14$ ${1.141}$ $0.767$ $\mathbf{1.172}$ $0.439$ $0.601$ $0.596$
$\mathbf{0.691}$ $0.646$ ARDS 1 - - - - - $0.612$ $0.631$ $0.726$ $0.661$
$0.722$ $0.601$ $\mathbf{0.768}$ 2 $1.25$ $1.228$ $1.283$ $0.581$
$\mathbf{1.312}$ $0.628$ $0.676$ $0.638$ $\mathbf{0.758}$ $0.73$ 3 $1.17$ NA
$1.171$ $1.156$ $\mathbf{1.282}$ $0.644$ NA $0.666$ $\mathbf{0.766}$ $0.708$ 4
$1.154$ NA $1.119$ $1.114$ $\mathbf{1.262}$ $0.616$ NA $0.635$ $0.697$
$\mathbf{0.744}$ WID-M 1 - - - - - $0.711$ $0.703$ $0.853$ $0.814$ $0.853$
$0.686$ $\mathbf{0.883}$ 2 $1.285$ $1.23$ $\mathbf{1.571}$ $1.438$ $1.534$
$0.731$ $0.739$ $0.8$ $0.846$ $\mathbf{0.883}$ 3 $1.328$ NA $1.501$ $1.404$
$\mathbf{1.514}$ $0.709$ NA $0.809$ $0.853$ $\mathbf{0.874}$ 4 $1.41$ NA
$1.388$ $1.363$ $\mathbf{1.469}$ $0.691$ NA $0.806$ $\mathbf{0.865}$ ${0.859}$
Diabetes 1 - - - - - $0.566$ $0.551$ $0.58$ $0.574$ $0.582$ ${0.578}$
$\mathbf{0.587}$ 2 $1.633$ ${1.554}$ ${1.707}$ $1.663$ $\mathbf{1.802}$ $0.53$
$0.566$ $0.567$ ${0.581}$ $\mathbf{0.587}$ 3 $1.593$ $\mathbf{1.53}$
$\mathbf{1.698}$ $1.245$ $1.67$ $0.514$ $0.568$ $0.563$ ${0.579}$
$\mathbf{0.585}$ 4 $\mathbf{1.611}$ $1.398$ $1.578$ $1.381$ ${1.609}$ $0.507$
$0.569$ $0.563$ ${0.581}$ $\mathbf{0.586}$ CIC-LOS 1 - - - - - $0.646$ $0.659$
$0.652$ $0.639$ $0.642$ - $\mathbf{0.663}$ 2 $1.042$ $1.003$ $\mathbf{1.148}$
- $1.101$ $0.575$ $0.632$ $0.648$ - $\mathbf{0.672}$ 3 $1.038$ $0.99$
$\mathbf{1.052}$ - ${0.925}$ $0.567$ $0.636$ $0.642$ - $\mathbf{0.664}$ 4
$\mathbf{0.995}$ NA $0.955$ - ${0.871}$ $0.539$ NA $0.64$ - $\mathbf{0.664}$

Table 2: Clustering and Classification performance. Best values in bold. NA
indicates no results due to an empty cluster. Note that $\operatorname{HTFD}$
values are not defined for $k=1$.

###  5.2 Classification and Clustering Performance

####  5.2.1 Baselines

As baselines for the classification task, we use 3 different kinds of
techniques. The first is a feedforward neural network (baseline) that only
performs classification. It’s architecture is set to be identical to that of a
combination of ExpertNet’s encoder and a single local network. The second is
the Supervised Autoencoder (SAE) Le et al. (2018) that uses reconstruction
loss as an unsupervised regularizer (similar architecture as baseline). The
third category uses the common ‘cluster-then-predict’ approach, where
clustering is independently performed first and classifiers are trained on
each cluster (denoted by -Z). In this category, we compare with $3$ clustering
methods $k$-means (where we use an autoencoder to get embeddings which are
then clustered using $k$-means), Deep Clustering Network DCN Yang (2017) and
Improved Deep Embedded Clustering (IDEC) Guo et al. (2017). We also use Deep
Mixture Neural Networks (DMNN) Li et al. (2020b) that follows this paradigm.
Note that their implementation only supports binary classification. We use
stochastic cohort sampling during prediction in all baselines that use
clustering for a fair comparison. We compare the clustering performance
obtained by ExpertNet with that of DMNN, $k$-means, DCN and IDEC.

####  5.2.2 Performance Metrics

Standard classification metrics, Area Under the Receiver Operating
Characteristic (AUC) and F1 scores, are used for binary classification. For
multiclass setting, we use one-vs-rest algorithm to calculate AUC.

To evaluate clustering we use Silhouette scores and another score, HTFD,
described below, that evaluates feature discrimination in the inferred
clusters. A common practice in clustering studies (e.g., Li et al. (2015)) is
to check, for each feature, if there is a statistically significant difference
in its distribution across the clusters. A low p-value ($<0.05$) indicates
significant difference. To aggregate this over all features $F$, we define,
for each cluster in a clustering, the metric Hypothesis Testing based Feature
Discrimination ($\operatorname{HTFD}$):

$\operatorname{HTFD}(C_{i})=\frac{1}{|F|}\sum_{f\in
F}-\ln\left(\text{p-value}(X_{i}^{f},X^{f})\right)*0.05$

where $X_{i}^{f}$ denotes the values of feature $f$ for data points in cluster
$C_{i}$ and $X^{f}$ denotes the feature values of data points in all clusters
except $C_{i}$. Student’s t-test is used to obtain the p-value. The negative
logarithm of p-value is multiplied by the significance level, to normalize and
obtain a measure wherein higher values indicate better clustering. To obtain
an overall value for the entire clustering, we take the average of individual,
cluster-wise HTFD values.

####  5.2.3 Hyperparameter Settings

For DCN-Z and IDEC-Z, we use default parameters as suggested by their authors.
For ExpertNet we let $(\beta,\gamma,\delta)=(0.5,1.5,1)$. We select these
default values by considering the sensitivity analysis (see Fig. 2). The
common encoder has layers of size 128-64-32 and local expert network has
layers of size 64-32-16-8. The size of latent embeddings is $20$. We evaluate
all the methods for four different values of $K=1,2,3,4$.

####  5.2.4 Results

Table 2 shows the performance of all methods compared, on classification and
clustering. We observe that cluster-then-predict methods (*-Z) and DMNN
generally perform better than SAE, which suggests that clustering-based
regularization is more effective than reconstruction-based regularization. SAE
outperforms the baseline on most datasets. These results align with previous
research that show that unsupervised regularization aids supervised learning.
ExpertNet outperforms all methods on all datasets for at least one input
cluster size. Also note that ExpertNet’s performance does not degrade with
increasing number of clusters as seen for KMeans-Z. Overall, for
classification, ExpertNet consistently outperforms all the baselines on all
datasets.

With respect to clustering, the performance of ExpertNet is superior to the
best baseline in 5 datasets, for some values of $k$. For other values of $k$,
and on other datasets, the performance values are comparable or lower. F1
scores and Silhouette scores are in Appendix B, where the performance trends
are similar. Overall, the results show that ExpertNet achieves clustering
performance that is comparable to, and achieves classification performance
that is considerably better than, the state-of-the-art alternatives
respectively.

###  5.3 Sensitivity Analysis and Ablation Studies

We evaluate the effect of hyperparameters $\beta,\gamma$ and $\delta$ on
ExpertNet. We individually vary each hyperparameter while setting other two to
$0$ and measure the classification performance. Figures 2(a), 2(b) and 2(c)
show the results for the CIC dataset. We observe that both the F1 and AUC
values are fairly robust to changes in their values.

Our stochastic cohort sampling approach may or may not be used independently
during training and prediction. To evaluate it’s effect we evaluate all four
combinations through an ablation study. We denote the combinations by TT, TF,
FT and FF, where the first and second positions indicate training and
prediction respectively. T indicates use of our approach while F indicates
that it is not used. Figure 2(d) and 2(e) show the F1 and AUC scores for all 4
combinations on the CIC dataset (results on Sepsis dataset in Appendix C). The
best performance is achieved when the approach is used both in training and
prediction (TT). For clustering, there is no prediction. Figure 2(f) shows
that the performance is better with rather than without sampling. All the
results shown are averages over $5$ runs.

###  5.4 Case Study: Mortality Prediction

As a case study, we illustrate the use of ExpertNet on the CIC mortality
prediction data for $k=3$ clusters. Since clustering is done simultaneously
with classification, the clusters are influenced by the target label, i.e.,
mortality indicator, and thus, by design, ExpertNet is expected to find
mortality subtypes. In other words, we expect the inferred clusters to have
different risk factors tailored to each underlying subpopulation. To evaluate
this, we examine feature importances for each cluster’s local risk model. We
distil the knowledge of the local networks into a simpler student model Gou et
al. (2021), a Gradient Boosting Classifier, in our case, that provides feature
importance values.

$|C_{1}|=2458$ | $|C_{2}|=1890$ | $|C_{3}|=2402$
---|---|---
$\%D=0.115$ | $\%D=0.032$ | $\%D=0.254$
Age | Age | GCS_last
GCS_last | UrineOutputSum | BUN_last
BUN_last | GCS_last | Age
RespRate_median | BUN_first | Lactate_last
BUN_first | CSRU | Bilirubin_last
Weight_last | GCS_lowest | Length_of_stay
HR_highest | MechVentDuration | GCS_median
Weight_first | BUN_last | SOFA
Weight | RespRate_median | Weight
RespRate_highest | HR_highest | HCO3_last
Table 3: Important Features for mortality prediction in respective clusters.
Features common in all three clusters are highlighted in yellow while those
common in two are highlighted in purple. Rest are unique to their respective
clusters.

In Table 3, we list the cluster sizes $C_{i}$, proportion of patients who do
not survive ($\%D$) and the top 10 most important features in each cluster. We
see that, as expected, the risk models created by ExpertNet deem different
sets of features as important for predicting mortality. Out of the $10$ most
important features, each risk model contains $3$ common features, $4$, $3$ and
$1$ features common across two models respectively and $3$, $4$ and $6$
features unique to respective clusters. Appendix F presents further analysis
of the clusters.

##  6 Conclusion

We design ExpertNet a model for combined clustering and classification and
theoretically analyze its generalization properties. Our model can be viewed
as a mixture of expert networks trained on inferred clusters in the data. Our
experiments show that both regularization through unsupervised clustering and
stochastic sampling strategy during training lead to substantial improvement
in classification performance. We demonstrate the efficacy of ExpertNet on
several clinical datasets, for predictive modeling tailored to subpopulations
inferred from the data.

The clustering performance of ExpertNet is comparable to that of other deep
clustering methods and may be improved further. This can be explored in future
work along with ways to combine hierarchical clustering algorithms with
supervised models and applications in other domains.

## References

  * Bartlett and Mendelson [2002] P. L. Bartlett and S. Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  JMLR, 2002.
  * Bartlett et al. [2017] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In NeurIPS, 2017.
  * Baxter [1995] Jonathan Baxter.  Learning internal representations.  In Proceedings of the eighth annual conference on Computational learning theory, pages 311–320, 1995.
  * Bengio et al. [2007] Y. Bengio, P. Lamblin, D. Popovici, and H. Larochelle.  Greedy layer-wise training of deep networks.  In NeurIPS, pages 153–160, 2007.
  * Caron et al. [2018] M. Caron, P. Bojanowski, A. Joulin, and M. Douze.  Deep clustering for unsupervised learning of visual features.  In ECCV, pages 132–149, 2018.
  * Caruana [1997] Rich Caruana.  Multitask learning.  Machine learning, 28(1):41–75, 1997.
  * Fei et al. [2020] H. Fei, Y. Ren, and D. Ji.  Mimic and conquer: Heterogeneous tree structure distillation for syntactic NLP.  In EMNLP 2020, pages 183–193, Online, November 2020.
  * Finley and Joachims [2008] T. Finley and T. Joachims.  Supervised k-means clustering.  2008\.
  * Fu et al. [2010] Zhouyu Fu, Antonio Robles-Kelly, and Jun Zhou.  Mixing linear svms for nonlinear classification.  IEEE Transactions on Neural Networks, 2010.
  * Golowich et al. [2018] Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  In Conference On Learning Theory, pages 297–299. PMLR, 2018.
  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * Gou et al. [2021] J. Gou, B. Yu, S. J. Maybank, and D. Tao.  Knowledge distillation: A survey.  International Journal of Computer Vision, 129(6):1789–1819, 2021\.
  * Gu and Han [2013] Quanquan Gu and Jiawei Han.  Clustered support vector machines.  In Artificial Intelligence and Statistics, 2013.
  * Guo et al. [2017] Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin.  Improved deep embedded clustering with local structure preservation.  In IJCAI, 2017.
  * Ibrahim et. al. [2020] Zina Ibrahim et. al.  On classifying sepsis heterogeneity in the icu: insight using machine learning.  JAMIA, 2020.
  * Jitta and Klami [2018] A. Jitta and A. Klami.  On controlling the size of clusters in probabilistic clustering.  In AAAI, 2018.
  * Johnson [2012] A. EW et.al. Johnson.  Patient specific predictions in the intensive care unit using a bayesian ensemble.  In CinC, 2012.
  * Koltchinskii and Panchenko [2002] V. Koltchinskii and D. Panchenko.  Empirical margin distributions and bounding the generalization error of combined classifiers.  The Annals of Statistics, 30(1):1–50, 2002.
  * Lasko et al. [2013] Thomas A Lasko, Joshua C Denny, and Mia A Levy.  Computational phenotype discovery using unsupervised feature learning over noisy, sparse, and irregular clinical data.  PloS one, 2013.
  * Le et al. [2018] Lei Le et al.  Supervised autoencoders: Improving generalization performance with unsupervised regularizers.  NeurIPS, 31:107–117, 2018.
  * Lee et. al. [2020] M. Lee et. al.  WiDS (Women in Data Science) Datathon 2020: ICU Mortality Prediction, 2020.
  * Li et al. [2020a] J. Li, P. Zhou, C. Xiong, and S. Hoi.  Prototypical contrastive learning of unsupervised representations.  arXiv preprint arXiv:2005.04966, 2020.
  * Li et al. [2020b] Xiangrui Li, Dongxiao Zhu, and Phillip Levy.  Predicting clinical outcomes with patient stratification via deep mixture neural networks.  AMIA Summits on Translational Science, 2020.
  * Li et al. [2015] Li Li et al.  Identification of type 2 diabetes subgroups through topological analysis of patient similarity.  Science translational medicine, 7(311):311ra174–311ra174, 2015\.
  * Lichman. [2013] M. Lichman.  Uci repository.  UCI, 2013.
  * Masoudnia and Ebrahimpour [2014] Saeed Masoudnia and Reza Ebrahimpour.  Mixture of experts: a literature survey.  Artificial Intelligence Review, 42(2):275–293, 2014.
  * Mohri et al. [2012] M. Mohri, A. Rostamizadeh, and A. Talwalkar.  Foundations of machine learning.  MIT Press, 2012.
  * Morrill [2019] J. et. al. Morrill.  The signature-based model for early detection of sepsis from electronic health records in the intensive care unit.  In CinC, 2019.
  * Rasmus et. al. [2015] A. Rasmus et. al.  Semi-supervised learning with ladder networks.  arXiv:1507.02672, 2015.
  * Reyna et. al. [2019] M. A Reyna et. al.  Early prediction of sepsis from clinical data: the physionet/computing in cardiology challenge.  In CinC, 2019.
  * Silva [2012] Ikaro et. al. Silva.  Predicting in-hospital mortality of icu patients: The physionet/computing in cardiology challenge 2012.  Computing in cardiology, 2012.
  * Suresh et al. [2018] Harini Suresh, Jen J Gong, and John V Guttag.  Learning tasks for multitask learning: Heterogenous patient populations in the icu.  In SIGKDD, 2018.
  * V. D. Maaten and Hinton [2008] L. V. D. Maaten and G. Hinton.  Visualizing data using t-sne.  JMLR, 9(11), 2008.
  * Xie et al. [2016] J. Xie, R. Girshick, and A. Farhadi.  Unsupervised deep embedding for clustering analysis.  In ICML, pages 478–487. PMLR, 2016.
  * Yang [2017] Bo et. al. Yang.  Towards k-means-friendly spaces: Simultaneous deep learning and clustering.  In ICML, pages 3861–3870. PMLR, 2017.
  * Zhang et al. [2016] Y. Zhang, K. Lee, and H. Lee.  Augmenting supervised neural networks with unsupervised objectives for large-scale image classification.  In ICML, pages 612–621. PMLR, 2016.
  * Zhao [2015] J. et. al. Zhao.  Stacked what-where auto-encoders.  arXiv preprint arXiv:1506.02351, 2015.

##  Appendix A Analysis

###  A.1 General case

The following lemma is from [Bartlett and Mendelson, 2002; Mohri et al., 2012,
Theorem 3.1]:

######  Lemma 1.

Let $\mathcal{F}$ be a set of maps $x\mapsto f(x)$. Suppose that
$0\leq\ell\left(q,y\right)\leq\lambda$ for any
$q\in\\{f(x):f\in\mathcal{F},x\in\mathcal{X}\\}$ and $y\in\mathcal{Y}$. Then,
for any $\delta>0$, with probability at least $1-\delta$ (over an i.i.d. draw
of $N$ i.i.d. samples $((x_{i},y_{i}))_{i=1}^{N}$), the following holds: for
all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]\leq\frac{1}{N}\sum_{i=1}^{N}\ell(f(x_{i}),y_{i})+2\hat{\mathcal{R}}_{N}(\ell\circ\mathcal{F})+3\lambda\sqrt{\frac{\ln(1/\delta)}{2N}},$
(7)

where
$\hat{\mathcal{R}}_{N}(\ell\circ\mathcal{F}):=\mathbb{E}_{\sigma}[\sup_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}\ell(f(x_{i}),y_{i})]$
and $\sigma_{1},\dots,\sigma_{N}$ are independent uniform random variables
taking values in $\\{-1,1\\}$.

We can use Lemma 1 to prove the following:

######  Theorem 2.

Let $\mathcal{F}_{j}$ be a set of maps $x\in\Omega_{j}\mapsto f_{j}(x)$. Let
$\mathcal{F}=\\{x\mapsto
f(x):f(x)=\sum_{j=1}^{K}\mathbbm{1}\\{x\in\Omega_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$.
Suppose that $0\leq\ell\left(q,y\right)\leq\lambda_{j}$ for any
$q\in\\{f(x):f\in\mathcal{F}_{j},x\in\Omega_{j}\\}$ and $y\in\mathcal{Y}_{j}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, the following
holds: for all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{N_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(k/\delta)}{2N_{j}}}\right),$
(8)

where
$\hat{\mathcal{R}}_{N}(\ell\circ\mathcal{F}_{j}):=\mathbb{E}_{\sigma}[\sup_{f_{j}\in\mathcal{F}_{j}}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}\ell(f_{j}(x_{i}),y_{i})]$
and $\sigma_{1},\dots,\sigma_{N}$ are independent uniform random variables
taking values in $\\{-1,1\\}$.

###### Proof of Theorem 2.

We have that

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]$
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell(f(x),y)\mid
x\in\Omega_{j})]$ (9)
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid
x\in\Omega_{j})].$

Since the conditional probability distribution is a probability distribution,
we apply Lemma 1 to each term and take union bound to obtain the following:
for any $\delta>0$, with probability at least $1-\delta$, for all
$j\in\\{1,\dots,k\\}$ and all $f_{j}\in F_{j}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid x\in\Omega_{j})]$
$\displaystyle\leq\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell(f_{j}(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{N_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(k/\delta)}{2N}}$
$\displaystyle=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{N_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(k/\delta)}{2N}}.$

Thus, using (9), we sum up both sides with the factors $\Pr(x\in\Omega_{j})$
to yield:

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]$
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid
x\in\Omega_{j})]$ (10)
$\displaystyle\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{N_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(k/\delta)}{2N}}\right).$
(11)

∎

###  A.2 Special case: multi-class classification

For multi-class classification problems with $\mathcal{B}$ classes and
$y\in\\{1,\dots,\mathcal{B}\\}$, define the margin loss as follows:

${\ell}_{\rho}(f(x),y)={\ell}_{\rho}^{(2)}({\ell}_{\rho}^{(1)}(f(x),y))$

where

${\ell}_{\rho}^{(1)}(f(x),y)=f(x)_{y}-\max_{y\neq
y^{\prime}}f(x)_{y^{\prime}}\in\mathbb{R},$

and

${\ell}_{\rho}^{(2)}(q)=\begin{cases}0&\text{if }\rho\leq q\\\
1-q/\rho&\text{if }0\leq q\leq\rho\\\ 1&\text{if }q\leq 0.\\\ \end{cases}$

Define the 0-1 loss as:

$\textstyle\ell_{01}(f(x),y)=\mathbbm{1}\\{y\neq\mathop{\mathrm{argmax}}_{y^{\prime}\in[T]}f(x)_{y^{\prime}}\\},$

where $[T]=\\{1,\dots,\mathcal{B}\\}$. For any $\rho>0$, the margin loss
${\ell}_{\rho}(f(x),y)$ is an upper bound on the 0-1 loss: i.e.,
${\ell}_{\rho}(f(x),y)\geq\ell_{01}(f(x),y)$.

The following lemma is from [Mohri et al., 2012, Theorem 8.1]:

######  Lemma 2.

Let $\mathcal{F}$ be a set of maps $x\mapsto f(x)$. Fix $\rho>0$. Then, for
any $\delta>0$, with probability at least $1-\delta$ over an i.i.d. draw of
$N$ i.i.d. test samples $((x_{i},y_{i}))_{i=1}^{m}$, the following holds: for
all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]\leq\frac{1}{N}\sum_{i=1}^{N}\ell_{\rho}(f(x_{i}),y_{i})+\frac{2\mathcal{B}^{2}}{\rho}\hat{\mathcal{R}}_{N}(\mathcal{F}_{\mathcal{B}})+\left(1+\frac{2\mathcal{B}^{2}}{\rho}\right)\sqrt{\frac{\ln(2/\delta)}{2N}},$

where $\mathcal{F}_{\mathcal{B}}=\\{x\mapsto
f(x)_{k}:f\in\mathcal{F},k\in[T]\\}$.

###### Proof.

Using Theorem 8.1 Mohri et al. [2012], we have that with probability at least
$1-\delta/2$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]\leq\frac{1}{N}\sum_{i=1}^{N}\ell_{\rho}(f(x_{i}),y_{i})+\frac{2\mathcal{B}^{2}}{\rho}\mathcal{R}_{N}(\mathcal{F}_{\mathcal{B}})+\sqrt{\frac{\ln(2/\delta)}{2N}},$

Since changing one point in $S$ changes
$\hat{\mathcal{R}}_{m}(\mathcal{F}_{\mathcal{B}})$ by at most $1/N$,
McDiarmid’s inequality implies the statement of this lemma by taking union
bound. ∎

######  Theorem 3.

Let $\mathcal{F}_{j}$ be a set of maps $x\in\Omega_{j}\mapsto f_{j}(x)$. Let
$\mathcal{F}=\\{x\mapsto
f(x):f(x)=\sum_{j=1}^{k}\mathbbm{1}\\{x\in\Omega_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$.
Suppose that $0\leq\ell\left(q,y\right)\leq\lambda_{j}$ for any
$q\in\\{f(x):f\in\mathcal{F}_{j},x\in\Omega_{j}\\}$ and $y\in\mathcal{Y}_{j}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, the following
holds: for all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2\mathcal{B}^{2}}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{T,j})+\left(1+\frac{2\mathcal{B}^{2}}{\rho}\right)\sqrt{\frac{\ln(2k/\delta)}{2N_{j}}}\right),$
(12)

where
$\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{T,j}):=\mathbb{E}_{\sigma}[\sup_{f_{j}\in\mathcal{F}_{T,j}}\frac{1}{N}\sum_{i=1}^{N_{j}}\sigma_{i}\ell(f_{j}(x_{i}^{j}),y_{i}^{j})]$
and $\sigma_{1},\dots,\sigma_{N}$ are independent uniform random variables
taking values in $\\{-1,1\\}$. Here, $\mathcal{F}_{\mathcal{B},j}=\\{x\mapsto
f(x)_{k}:f\in\mathcal{F}_{j},k\in[\mathcal{B}]\\}$.

###### Proof of Theorem 2.

We have that

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]$
$\displaystyle=\sum_{j=1}^{K}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f(x),y)\mid
x\in\Omega_{j})]$ (13)
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid
x\in\Omega_{j})].$

Since the conditional probability distribution is a probability distribution,
we apply Lemma 1 to each term and take union bound to obtain the following:
for any $\delta>0$, with probability at least $1-\delta$, for all
$j\in\\{1,\dots,k\\}$ and all $f_{j}\in F_{j}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid x\in\Omega_{j})]$
$\displaystyle\leq\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f_{j}(x_{i}^{j}),y_{i}^{j})+\frac{2\mathcal{B}^{2}}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{\mathcal{B},j})+\left(1+\frac{2\mathcal{B}^{2}}{\rho}\right)\sqrt{\frac{\ln(2k/\delta)}{2N}}$
$\displaystyle=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2\mathcal{B}^{2}}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{\mathcal{B},j})+\left(1+\frac{2\mathcal{B}^{2}}{\rho}\right)\sqrt{\frac{\ln(2k/\delta)}{2N}}.$

Thus, using (13), we sum up both sides with the factors $\Pr(x\in\Omega_{j})$
to yield:

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]$
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid
x\in\Omega_{j})]$ (14)
$\displaystyle\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2\mathcal{B}^{2}}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{\mathcal{B},j})+\left(1+\frac{2\mathcal{B}^{2}}{\rho}\right)\sqrt{\frac{\ln(2k/\delta)}{2N}}\right).$
(15)

∎

###  A.3 Special case: deep neural networks with binary classification

Note that for any $\rho>0$, the margin loss ${\ell}_{\rho}(f(x),y)$ is an
upper bound on the 0-1 loss: i.e.,
${\ell}_{\rho}(f(x),y)\geq\ell_{01}(f(x),y)$.

The following lemma is from [Mohri et al., 2012, Theorem 4.4]:

######  Lemma 3.

Let $\mathcal{F}$ be a set of real-valued functions. Fix $\rho>0$. Then, for
any $\delta>0$, with probability at least $1-\delta$ over an i.i.d. draw of
$m$ i.i.d. test samples $((x_{i},y_{i}))_{i=1}^{m}$, the following holds: for
all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]\leq\frac{1}{m}\sum_{i=1}^{m}\ell_{\rho}(f(x_{i}),y_{i})+\frac{2}{\rho}\hat{\mathcal{R}}_{m}(\mathcal{F})+3\sqrt{\frac{\ln(2/\delta)}{2m}}.$

######  Theorem 4.

Let $\mathcal{F}_{j}$ be a set of maps $x\in\Omega_{j}\mapsto f_{j}(x)$. Let
$\mathcal{F}=\\{x\mapsto
f(x):f(x)=\sum_{j=1}^{K}\mathbbm{1}\\{x\in\Omega_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$.
Suppose that $0\leq\ell\left(q,y\right)\leq\lambda_{j}$ for any
$q\in\\{f(x):f\in\mathcal{F}_{j},x\in\Omega_{j}\\}$ and $y\in\mathcal{Y}_{j}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, the following
holds: for all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{j})+3\sqrt{\frac{\ln(2/\delta)}{2N_{j}}}\right),$
(16)

where
$\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{j}):=\mathbb{E}_{\sigma}[\sup_{f_{j}\in\mathcal{F}_{j}}\frac{1}{N}\sum_{i=1}^{N_{j}}\sigma_{i}\ell(f_{j}(x_{i}^{j}),y_{i}^{j})]$
and $\sigma_{1},\dots,\sigma_{N}$ are independent uniform random variables
taking values in $\\{-1,1\\}$.

###### Proof of Theorem 4.

We have that

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]$
$\displaystyle=\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f(x),y)\mid
x\in\Omega_{j})]$ (17)
$\displaystyle=\sum_{j=1}^{K}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid
x\in\Omega_{j})].$

Since the conditional probability distribution is a probability distribution,
we apply Lemma 3 to each term and take union bound to obtain the following:
for any $\delta>0$, with probability at least $1-\delta$, for all
$j\in\\{1,\dots,k\\}$ and all $f_{j}\in F_{j}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid x\in\Omega_{j})]$
$\displaystyle\leq\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f_{j}(x_{i}^{j}),y_{i}^{j})+\frac{2}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{j})+3\sqrt{\frac{\ln(2/\delta)}{2N_{j}}}$
$\displaystyle=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{j})+3\sqrt{\frac{\ln(2/\delta)}{2N_{j}}}.$

Thus, using (17), we sum up both sides with the factors $\Pr(x\in\Omega_{j})$
to yield:

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]$
$\displaystyle=\sum_{j=1}^{K}\Pr(x\in\Omega_{j})\mathbb{E}_{x,y}[\ell_{01}(f_{j}(x),y)\mid
x\in\Omega_{j})]$ (18)
$\displaystyle\leq\sum_{j=1}^{k}\Pr(x\in\Omega_{j})\left(\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2}{\rho}\hat{\mathcal{R}}_{N_{j}}(\mathcal{F}_{j})++3\sqrt{\frac{\ln(2/\delta)}{2N_{j}}}\right).$
(19)

∎

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

Using Theorem 4 with $\Pr(x\in\Omega_{j})=1/k$ and $m_{j}=N/k$, for
$f\in\mathcal{F}^{k}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]$
$\displaystyle\leq\frac{1}{k}\sum_{j=1}^{k}\left(\frac{1}{(N/k)}\sum_{i=1}^{N/k}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+2\rho^{-1}\hat{\mathcal{R}}_{N/k}(\mathcal{F}_{j})+3\sqrt{\frac{\ln(2/\delta)}{2(N/k)}}\right)$
$\displaystyle=\frac{1}{k}\sum_{j=1}^{k}\left(\frac{k}{N}\sum_{i=1}^{N/k}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+2\rho^{-1}\hat{\mathcal{R}}_{N/k}(\mathcal{F}_{j})+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}\right)$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{k}\sum_{i=1}^{N/k}\ell_{\rho}(f(x_{i}^{j}),y_{i}^{j})+\frac{2\rho^{-1}}{k}\sum_{j=1}^{k}\hat{\mathcal{R}}_{N/k}(\mathcal{F}_{j})+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}$
$\displaystyle=\hat{\mathbb{E}}_{x,y}[\ell_{\rho}(f(x),y)]+\frac{2\rho^{-1}}{k}\sum_{j=1}^{k}\hat{\mathcal{R}}_{N/k}(\mathcal{F}_{j})+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}$

Here, using Theorem 1 of Golowich et al. [2018], we have that

$\hat{\mathcal{R}}_{N/k}(\mathcal{F}_{j})\leq\frac{B_{j}\sqrt{k}(\sqrt{2\log(2)(L+Q)}+1)(\prod_{l=1}^{L}M_{l}^{j})(\prod_{l=1}^{Q}M_{l}^{0})}{\sqrt{N}}.$

Thus, for any $\delta>0$, with probability at least $1-\delta$ over an i.i.d.
draw of $N$ i.i.d. test samples $((x_{i},y_{i}))_{i=1}^{N}$, the following
holds: for all maps $f\in\mathcal{F}^{K}$,

$\displaystyle\mathbb{E}_{x,y}[\ell_{01}(f(x),y)]-\hat{\mathbb{E}}_{x,y}[\ell_{\rho}(f(x),y)]$
$\displaystyle\leq\frac{2\rho^{-1}}{K}\sum_{j=1}^{K}\frac{B_{j}\sqrt{k}(\sqrt{2\log(2)(L+Q)}+1)(\prod_{l=1}^{L}M_{l}^{j})(\prod_{l=1}^{Q}M_{l}^{0})}{\sqrt{N}}+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}$
$\displaystyle\leq\frac{2\rho^{-1}(\sqrt{2\log(2)(L+Q)}+1)(\prod_{l=1}^{Q}M_{l}^{0})\left(\sum_{j=1}^{k}B_{j}\prod_{l=1}^{L}M_{l}^{j}\right)}{\sqrt{kN}}+3\sqrt{\frac{k\ln(2k/\delta)}{2N}}$

∎

By taking union bound over $M_{l}^{j}$, it is straightforward to replace
$\prod_{l=1}^{L}M_{l}^{j}$ by $\prod_{l=1}^{L}\|W_{l}^{j}\|_{F}$ in the bound
of Theorem 1 with additional factors that is not dominant and hidden in the
$\tilde{O}$ notation (see the proof of Lemma A.9 of Bartlett et al. [2017] or
the proof of Theorem 2 of Koltchinskii and Panchenko [2002]).

##  Appendix B Extended Results

SIL Dataset k KMeans DCN IDEC DMNN ExpertNet CIC 2 0.54 NA 0.51 0.125 0.358 3
0.297 NA 0.354 0.092 0.305 4 0.168 NA 0.326 0.085 0.231 Sepsis 2 0.588 0.253
0.325 0.250 0.357 3 0.277 0.242 0.406 0.104 0.349 4 0.212 NA 0.307 0.099 0.248
AKI 2 0.401 0.596 0.769 0.259 0.638 3 0.459 0.782 0.828 0.285 0.611 4 0.459
0.585 0.622 0.278 0.53 ARDS 2 0.369 0.65 0.746 0.295 0.484 3 0.384 NA 0.553
0.319 0.628 4 0.4 NA 0.856 0.301 0.76 WID-M 2 0.346 0.797 0.423 0.202 0.393 3
0.189 NA 0.45 0.157 0.282 4 0.136 NA 0.544 0.152 0.197 Diabetes 2 0.249 0.448
0.378 0.156 0.129 3 0.201 0.181 0.503 0.167 0.154 4 0.157 0.088 0.423 0.183
0.24 CIC_LOS 2 0.547 0.582 0.546 - 0.231 3 0.306 0.372 0.447 - 0.099 4 0.162
NA 0.349 - 0.129

Table 4: Silhouette Scores. Best values in bold.

F1 Dataset k Baseline SAE KMeans-Z DCN-Z IDEC-Z DMNN-Z ExpertNet CIC 1 0.436
0.487 0.617 0.629 0.628 0.299 0.678 2 0.639 NA 0.569 0.379 0.712 3 0.597 NA
0.606 0.413 0.693 4 0.432 NA 0.582 0.404 0.708 Sepsis 1 0.500 0.498 0.715
0.646 0.684 0.157 0.806 2 0.561 0.525 0.686 0.427 0.822 3 0.557 0.59 0.653
0.363 0.814 4 0.504 NA 0.612 0.537 0.815 AKI 1 0.506 0.417 0.57 0.528 0.578
0.382 0.638 2 0.333 0.529 0.527 0.645 0.642 3 0.459 0.569 0.541 0.647 0.625 4
0.361 0.571 0.574 0.640 0.605 ARDS 1 0.481 0.481 0.561 0.529 0.525 0.043 0.554
2 0.499 0.498 0.483 0.132 0.567 3 0.555 NA 0.492 0.143 0.564 4 0.548 NA 0.481
0.163 0.551 WID-M 1 0.520 0.514 0.644 0.581 0.65 0.026 0.696 2 0.604 0.497
0.621 0.331 0.694 3 0.582 NA 0.616 0.331 0.686 4 0.578 NA 0.606 0.360 0.686
Diabetes 1 0.471 0.438 0.491 0.436 0.486 0.226 0.465 2 0.438 0.421 0.468 0.235
0.493 3 0.468 0.401 0.439 0.280 0.447 4 0.453 0.393 0.451 0.279 0.46 CIC-LOS 1
0.399 0.427 0.433 0.403 0.431 - 0.458 2 0.354 0.371 0.409 - 0.456 3 0.324
0.394 0.403 - 0.46 4 0.292 NA 0.398 - 0.442

Table 5: F1 Scores. Best values in bold.

##  Appendix C Extended Ablation Analysis

(a) F1/AUC vs. $\beta$

(b) F1/AUC vs. $\gamma$

(c) SIL

Figure 3: Ablation study on Sepsis dataset. TT represents that stochastic
sampling is turned on in both training and testing phase. Similarly for other
combinations. Note that stochastic sampling turned on in the training phase
has a strong effect on performance.

##  Appendix D Data Preprocessing and Feature Extraction

We evaluate the results on $6$ real world clinical datasets out of which $3$
are derived from the MIMIC III dataset derived from Beth Israel Deaconess
Hospital. CIC dataset is derived from 2012 Physionet challenge Silva [2012] of
predicting in-hospital mortality of intensive care units. The Sepsis dataset
is derived from the 2019 Physionet challenge of sepsis onset prediction. We
manually extract the Acute Kidney Failure (AKI) and Acute Respiratory Distress
Syndrome (ARDS) datasets from the larger MIMIC III dataset. WID Mortality
dataset is extracted from the 2020 Women In Data Science challenge to predict
patient mortality. The Diabetes Readmission prediction dataset consists of
$100000$ records of patients. This is a multiclass version of the CIC dataset
where the Length of Stay (LOS) feature is discretized into $3$ classes using
quartiles. The task is to predict the LOS of ICU patients.

  * •

CIC: The CIC dataset is derived from the 2012 Physionet challenge Silva [2012]
of predicting in-hospital mortality of intensive care units (ICU) patients at
the end of their hospital stay. The data has time-series records, comprising
various physiological parameters of $12000$ patient ICU stays. We follow the
data processing scheme of Johnson [2012] (the top ranked team in the
competition) to obtain static 117-dimensional features for each patient.

  * •

Sepsis: The Sepsis dataset is derived from the 2019 Physionet challenge of
sepsis onset prediction. The dataset has time-series records, comprising
various physiological parameters of $\sim 40000$ patients. We follow the data
processing scheme of the competition winners Morrill [2019] to obtain static
89 dimensional features for each patient.

  * •

AKI and ARDS: We manually extract the Acute Kidney Failure (AKI) and Acute
Respiratory Distress Syndrome (ARDS) datasets from the larger MIMIC III
dataset. We follow the KDIGO criteria to determine kidney failure onset time
and the Berlin criteria for ARDS. The challenge is to predict kidney failure
onset ahead of time. Similar to the above datasets, we derive static vectors
from the time series data.

  * •

WID Mortality: This dataset is extracted from the 2020 Women In Data Science
challenge where the objective is to create a model that uses data from the
first 24 hours of intensive care to predict patient survival. We perform
standard data cleaning procedures before using the dataset.

  * •

Diabetes: The Diabetes Readmission prediction dataset consists of $100000$
records of patients from 130 hospitals in the US from the year 1998 to 2008.

  * •

CIC-LOS: This is a multiclass version of the CIC dataset where the Length of
Stay (LOS) feature is discretized into $3$ classes using quartiles. The task
is to predict the LOS of ICU patients.

##  Appendix E ExpertNet Optimization Details

###  E.1 Updating ExpertNet parameters

Optimizing $(\mathcal{U},\mathcal{V})$ is similar to training an SAE - but
with the additional loss terms $L_{c},L_{s}$ and $L_{bal}$. We code our
algorithm in PyTorch which allows us to easily backpropagate all the losses
simultaneously. To implement SGD for updating the network parameters, we look
at the problem w.r.t. the incoming data $x_{i}$:

$\displaystyle\min_{\mathcal{U},\mathcal{W}}L^{i}=\ell(g(f(x_{i})),x_{i})+\beta\cdot\operatorname{KL}(P,Q)$
$\displaystyle+\gamma\cdot\sum_{j=1}^{k}q_{i,j}\operatorname{CE}(y_{i},h_{j}(x_{i};\mathcal{V}_{j}))+\delta\cdot
L_{bal}$

The gradient of the above function over the network parameters is easily
computable. Let $\mathcal{J}=(\mathcal{U},\mathcal{V},\mathcal{W})$ be the
collection of network parameters, then for a fixed target distribution $P$,
the gradients of $L_{c}$ w.r.t. embedded point $z_{i}$ and cluster center
$\mu_{j}$ can be computed as:

$\displaystyle\frac{\partial L_{c}}{\partial
z_{i}}=2\sum_{j=1}^{k}\left(1+\left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}\left(p_{ij}-q_{ij}\right)\left(z_{i}-\mu_{j}\right)$
$\displaystyle\frac{\partial
L_{c}}{\partial\mu_{j}}=2\sum_{i}\left(1+\left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}\left(q_{ij}-p_{ij}\right)\left(z_{i}-\mu_{j}\right)$

The above derivations are from Xie et al. [2016]. We leverage the power of
automatic differentiation to calculate the gradients of $L_{bal}$ and $L_{s}$
during execution. Then given a mini batch with $m$ samples and learning rate
$\lambda,\mu_{j}$ is updated by:

$\displaystyle\mu_{j}=\mu_{j}-\frac{\tau}{m}\sum_{i=1}^{m}\frac{\partial
L_{c}}{\partial\mu_{j}}$ (20)

The decoder’s weights are updated by:

$\displaystyle\mathcal{V}=\mathcal{V}-\frac{\tau}{m}\sum_{i=1}^{m}\frac{\partial
L_{r}}{\partial\mathcal{V}}$ (21)

and the encoder’s weights are updated by:

$\displaystyle\mathcal{U}=\mathcal{U}-\frac{\tau}{m}\sum_{i=1}^{m}\left(\frac{\partial
L_{r}}{\partial\mathcal{U}}+\beta\frac{\partial
L_{c}}{\partial\mathcal{U}}+\gamma\frac{\partial
L_{s}}{\partial\mathcal{U}}+\delta\frac{\partial
L_{bal}}{\partial\mathcal{U}}\right)$ (22)

$\mathcal{J}\xleftarrow{}\mathcal{J}-\tau\nabla_{\mathcal{J}}L^{i}$

where $\tau$ is the diminishing learning rate.

##  Appendix F Case Study: Additional Analysis

Cluster 1 Cluster 2 Cluster 3 SAPS-I Length_of_stay SAPS-I SOFA CCU SOFA
GCS_first CSRU Length_of_stay GCS_lowest DiasABP_first Weight CSRU GCS_first
CSRU Creatinine_last Creatinine_last MechVentLast8Hour Creatinine_last
Glucose_first DiasABP_first GCS_last HR_first Glucose_first BUN_last MAP_first
HR_first Creatinine_first NIDiasABP_first MAP_first Lactate_first NIMAP_first
NIDiasABP_first

Table 6: Cluster wise features sorted by $\operatorname{HTFD}$ values.

We study the clusters found by ExpertNet by analyzing the
$\operatorname{HTFD}$ metric in table 6. SAPS-I and SOFA have high
$\operatorname{HTFD}$ in clusters $1$ and $3$. This indicates that the two
clusters have different distributions of SAPS-I and SOFA. It (SOFA) is also an
important feature for cluster $3$’s risk model (Table 3) but in distribution,
it is similar to SOFA values of clusters $2$ but not $1$. GCS_Last (Glasgow
Coma Score) is an important feature for all the three risk models but not
significantly different across the three clusters (cluster averages
$12.744,14.489,10.226$). Normal GCS is $15$.


# Exploring Parity Challenges in Reinforcement Learning through Curriculum
Learning with Noisy Labels

Bei Zhou  Søren Riis Correspondent author

###### Abstract

This paper delves into applying reinforcement learning (RL) in strategy games,
particularly those characterized by parity challenges, as seen in specific
positions of Go and Chess and a broader range of impartial games. We propose a
simulated learning process, structured within a curriculum learning framework
and augmented with noisy labels, to mirror the intricacies of self-play
learning scenarios. This approach thoroughly analyses how neural networks
(NNs) adapt and evolve from elementary to increasingly complex game positions.
Our empirical research indicates that even minimal label noise can
significantly impede NNs’ ability to discern effective strategies, a
difficulty that intensifies with the growing complexity of the game positions.
These findings underscore the urgent need for advanced methodologies in RL
training, specifically tailored to counter the obstacles imposed by noisy
evaluations. The development of such methodologies is crucial not only for
enhancing NN proficiency in strategy games with significant parity elements
but also for broadening the resilience and efficiency of RL systems across
diverse and complex environments.

##  1 Introduction

In combinatorial game theory, impartial games are characterised by positions
where players alternate turns, with both players able to move the same set of
pieces, thereby having access to the same set of legal moves. The mathematics
of this class of games is well-understood. According to the underlying theory
for these games, determining the values of the parity function plays a central
role in effectively assessing these positions and in identifying advantageous
moves.

Nim, a well-known two-player impartial game, exemplifies a key principle in
combinatorial game theory. As described by Berlekamp Berlekamp et al. (2001),
the Sprague–Grundy theorem establishes that any position in an impartial game
is mathematically equivalent to a position in Nim. In this game, positions are
defined by several heaps, each containing a specific number of counters.
Players alternate turns to remove counters from their chosen heaps, aiming to
be the last to empty the board and secure a win. This theorem also introduces
a method for assigning Grundy numbers, or nimbers, to game positions, which is
crucial for evaluating their strategic value. A position is deemed winning if
it has a non-zero Grundy number. The essence of Nim’s mathematical complexity
lies in determining these nimbers. Specifically, a position’s nimber in Nim is
the binary XOR sum of the nimbers of its subpositions, with a zero sum
indicating a losing position and a non-zero sum indicating a winning one.

The nim board positions can be represented by a list of bits, being 1, 0 or
-1, where 1 denotes the counters on the board, 0 denotes the counters being
removed from the board, and -1 is a token separating the heaps Zhou and Riis
(2022). To accommodate this nim board representation, we employ a variant of
the parity function, also called parity with noise, which is defined as
follows Banino et al. (2021). Let $n$ be any positive integer. Given input
$\\{x_{1},\ldots,x_{n}\\}=\\{0,1,-1\\}^{n}$, the function is defined as:

$f({x_{1},\ldots,x_{n}})=\left(\sum_{i=1}^{n}(x_{i}==1)\right)\ mod\ 2$ (1)

where $n$ is the length of the input. The function outputs either 0 or 1,
depending on whether the input bitstring contains even or odd numbers of 1s.
However, determining if a Nim position is winning is more complicated than
figuring out the parity of a board representation. With this or any given
board representation, evaluating a Nim board position involves recursively
applying the parity function to the number of counters on each heap. Thus, for
self-play RL algorithms to master Nim game or other impartial games, they must
learn a perfect parity function and know how to apply it to find the winning
move. But in some partisan games like Chess or Go, the PV-NNs in AlphaZero do
not have to be able to implicitly model a parity function on some positions
that involve using the parity function to determine the winning move because
after running some MCTS simulations, the best move can still be identified.

Prior work has concluded that learning a parity function with neural networks
from long bitstrings sampled from a uniform distribution is a challenge
Cornacchia and Mossel (2023); Abbe et al. (2023); Daniely and Malach (2020);
Shalev-Shwartz et al. (2017). Recent studies have explored ways to build non-
uniform distributions to make it learnable Cornacchia and Mossel (2023); Abbe
et al. (2023); Daniely and Malach (2020). We will summarise their results in
Section 2.

Noisy labels refer to mislabeled or incorrect labels in the training dataset.
In a supervised learning setting, one common approach to addressing noisy
labels is to use a surrogate loss function to minimize the impact of these
noisy labels and guide the model towards learning the underlying true patterns
in the data Song et al. (2022); Scott (2015); Scott et al. (2013); Natarajan
et al. (2013); Bylander (1994). Typically, these solutions with theoretical
assurances require prior knowledge of noise rates. Assuming the label noise is
homogeneous, Liu and Guo (2020) developed the peer loss that works without
knowing the noise rates.

In reinforcement learning systems, the reward an agent receives might not
reflect its true performance, thus misleading the agent due to the randomness
in the reward signal. Wang et al. (2020) outlined three sources of the noise
in the reward function, which are the noise in the environment, task-specific
noise and the noise from adversarial attacks. In these cases, measuring the
exact noise rates or making assumptions about the noise is extremely
difficult.

Nick (2014) demonstrated that in reinforcement learning, reward corruption
tends to hinder the performance of a wide range of agents and may lead to
disastrous consequences for highly intelligent agents. Everitt et al. (2017)
proved a theorem called No Free Lunch, leading to a strong conclusion that no
RL agent can outperform a random agent if the noisy rewards are arbitrary and
the RL agent does not make any assumption regarding the noise pattern.
Building on their results, Wang et al. (2020) introduced a reward estimator
with which an RL can learn in a noisy environment under perturbed reward, a
noisy reward model they came up with. Their RL agent can learn in this
scenario where the noises were generated by a reward confusion matrix because
the initial condition defined by the No Free Lunch theorem is violated. But
again, as they pointed out, solving an RL problem where the underlying noise
model is unknown and stochastic is a formidable challenge.

Deep reinforcement learning (DRL) algorithms combine RL algorithms with neural
networks that enable them to handle high-dimensional input spaces, exemplified
by the AlphaZero algorithm that achieved super-human performances on various
board games, including chess, Go and shogi. The AlphaZero algorithm utilises
two neural networks called the Policy and Value networks (PV-NNs) Silver et
al. (2018). In the self-play process, the algorithm generates training data by
playing against itself. In a self-play game, the states encountered by the
agent are labelled as winning states if they won the game; Otherwise, they are
treated as losing states Silver et al. (2016, 2017). In this process, some
losing states might be mislabeled as winning if the agent won, and vice versa.
This is referred to as the credit assignment problem where the RL agent
attributes the reward to the sequence of actions leading to the state where
this reward is received. The value network is trained on the actual game
output of the self-play simulations Silver et al. (2016), thus making it
susceptible to the credit assignment problem. The labels for training the
policy network come from the statistics of the Monte-Carlo Tree Search (MCTS)
simulations guided by the predictions from the PV-NNs Silver et al. (2016).
The incorrect evaluation of the value network could mislead the search and as
a consequence, the gathered statistics that the policy network is trained on
are also erroneous.

This credit assignment problem in AlphaZero-style learning, however, is, in
general, not a problem as the iterative nature of self-play allows the agent
to gradually improve and converge towards more accurate and effective
strategies over time. Additionally, it could also bring some extra benefits.
The noise in the labels can enhance exploration in the learning process,
allowing the algorithm to explore a broader range of moves and preventing it
from converging too quickly to a suboptimal solution. However, excessive
inaccuracies in the training labels could impede learning progress.

Our work aims to quantitatively measure to what extent neural networks
modelling parity function resist the wrong labels in the dataset across
bitstrings of varying length. This could provide more insights into
investigating the impact of the credit assignment problem in self-play
reinforcement learning algorithms that employ neural networks, like AlphaZero-
style algorithms on mastering impartial games.

Our results show that the appearance of more than 5% noisy labels impedes the
ability of the neural network to model a parity function on long bitstrings
(of length 100). This indicates that the wrong labels might challenge self-
play RL algorithms to master impartial games with large board positions.

The structure of this paper is as follows. Section 2 summarises recent studies
on the intricacies of modelling a parity function using various neural
networks. Section 3 explains our experiment setup and presents our results on
the noisy label problem in a simulated reinforcement learning setting. This
paper is concluded in Section 4.

##  2 Related Work

Learning the parity function using a neural network is a trivial task on short
bitstrings. One of our experiments showed that a single-layer Long Short-Term
Memory (LSTM) model with 16 nodes could model a perfect parity function on
uniformly sampled bitstrings of length 20. A request of research
111https://openai.com/research/requests-for-research-2 released by OpenAI
proposed a question with regards to using LSTM to model the parity function
under two different sets of bitstrings. One database consists of 100,000
random bitstrings of a fixed length of 50, whereas the other one contains the
same number of bitstrings, but the length of each bitstring is independently
and randomly chosen between 1 and 50. The results were with the first
database, the LSTM model failed to learn the parity function, but it succeeded
with the second dataset. Additionally, on the bitstrings with varying lengths,
the LSTM model tends to converge faster if it was fit in shorter bitstrings
than longer ones at the early training stage. This suggests that the
performance of the neural network in modelling the parity function is
influenced not only by the length of the bitstrings but also by the
distribution from which they are sampled.

Recent work has studied the effects of these two factors on neural networks’
ability to model a parity function. Shalev-Shwartz et al. (2017) has proved
that under uniformed data, the difficulty grows exponentially as the bitstring
length, and this challenge is shared among various neural network
architectures. The difficulty, however, can be eased under other specific data
distributions or other learning schemes.

###  2.1 Learning parity function with uniform data

Cornacchia and Mossel (2023); Abbe et al. (2023); Daniely and Malach (2020)
have highlighted that modelling a parity function from uniformly sampled long
bitstrings is extremely difficult. Shalev-Shwartz et al. (2017) proved it and
showed that this difficulty stems from the insufficient information conveyed
by the gradient with respect to the underlying function, which is in this case
the parity function. Here we summarise the main results from Shalev-Shwartz et
al. (2017).

Let $\mathcal{X}\in\\{0,1\\}^{n}$ be the instance space, and
$\mathcal{Y}\in\\{0,1\\}$ the label space. Given a dataset
$(\boldsymbol{X},\boldsymbol{y})$ where $\mathbf{x}\in\boldsymbol{X}$ is
uniformly sampled, let $h\in\mathbf{\mathcal{H}}$ be the underlying function
that maps $\boldsymbol{X}$ to $\boldsymbol{y}$, where $\mathbf{\mathcal{H}}$
represents all the $2^{n}$ possible functions over the instance space. The
parity function is one of the functions in $\mathbf{\mathcal{H}}$. We consider
a binary classification task that uses a neural network $p_{\mathbf{w}}$
parameterised by $\mathbf{w}$ to model the target function $h$ from this
database via gradient-based methods with loss function $\ell$ being hinge loss
or cross-entropy loss. This leads to an optimisation problem that can be
formalised as:

$\min_{\mathbf{w}}F_{h}(\textbf{w})=\min_{\mathbf{w}}\mathbb{E}_{\mathbf{x}}[{\ell}(p_{\mathbf{w}}(\mathbf{x}),h(\mathbf{x}))]$
(2)

The gradient $\nabla F_{h}(\textbf{w})$ concerning w holds useful information
about the target function $h$. They further studied the variance of $\nabla
F_{h}(\textbf{w})$ w.r.t the function $h$ randomly sampled from
$\mathbf{\mathcal{H}}$ to measure the expected amount of information about the
target function revealed by the gradient, and concluded that:

$\mathrm{Var}(\mathbf{\mathcal{H}},F,\mathbf{w})\leq\frac{G(\mathbf{w}^{2})}{|\mathbf{\mathcal{H}}|}=\frac{C}{2^{n}}$
(3)

where $G(\mathbf{w}^{2})$ is constant given w. So we denote it as a constant
$C$. This variance reduces exponentially as bitstring length increases,
indicating that when the length of the bitstring is sufficiently large, the
gradient at any point of w will be centred around a fixed point, resulting in
trapping the optimisation process in local optima. The variance is also
independent of the target function $h$, meaning that this result applies to
$h$ being the parity function. They further provided a lower upper bound on
the variance, given by

$\mathrm{Var}(\mathbf{\mathcal{H}},F,\mathbf{w})\leq
O(\mathrm{exp}(-\Omega(d))+\mathrm{exp}(-\Omega(r)))$ (4)

where $r$ is norm of $\mathbf{x}$, $||\mathbf{x}||$. This gave rise to the
conclusion that any neural network trained under gradient-based methods cannot
model the parity function when the bitstring length and $r$ are moderately
large. Their experiments show that the difficulty of learning the parity
function grows as the bitstring becomes longer, and their multi-layer
perception (MLP) model did not perform any better than random guessing when
the length of the bitstring reaches 30.

###  2.2 Learning parity function with non-uniform data

Although learning parity function under uniform data distribution on long
bitstrings faces strict constraints, some prior studies have shown that when
the bitstrings are not sampled uniformly, neural networks trained by gradient
descent methods can model the parity function efficiently with the data
sampled from certain distributions. Cornacchia and Mossel (2023) proposed a
new way to build the dataset in which the bitstrings are sampled from two or
more product distributions and the neural network is trained using curriculum
learning (CL), leading to a significant reduction in the computational cost of
learning the parity function. Abbe et al. (2023) further proved that learning
the parity function in the curriculum learning fashion provides certain
advantages over the standard training method where data are sampled uniformly.
In CL, the model is presented with spare examples at the early stage of
training after which the whole dataset is presented to the model. This enables
the model to learn some knowledge in the beginning and primes it to learn from
complex data.

Daniely and Malach (2020) emphasised learning parities under uniform
distribution is computationally challenging and thus constructed and used a
dataset sampled from a mixture of two distributions to make the parity
function learnable for neural networks using gradient descent methods.

Pondernet is a new type of neural network tested against modelling the parity
function Banino et al. (2021). To make the parity function learnable, in their
setting, the bitstrings of length $n$ are sampled in a way that a random
number of bits from 1 to $n$ were randomly set to 1 or -1 and the remaining
bits were set to 0. This approach establishes a latent curriculum where the
model is presented with a mix of spare and dense bitstrings in each training
batch. Here, the density of a bitstring is measured by Hamming weight, where
the hardness of a bitstring is defined by the number of 1 and -1 bits in it,
analogous to the measure used in Abbe et al. (2023).

###  2.3 Learning parity function with various NN architectures

Some prior works focused on constructing specific neural networks with fixed
weight parameters, mainly MLP or Recurrent Neural Networks (RNN), dedicated to
solving the parity problem Hohil et al. (1999); Liu et al. (2002); Franco and
Cannas (2001); Wilamowski et al. (2003); Franco and Cannas (2001). An RNN with
3 neurons and 12 frozen parameters can approximate an XOR function. These
artificially hard-wired neural networks can generalize to all seen and unseen
patterns without training or adaptation Al-Rawi (2005). However, it is
impossible to artificially set up the weight parameters for neural networks to
model the unknown data distributions.

Setting aside the impact of the distribution of bitstrings, most related
studies focused on investigating the inherent limitations of various neural
networks in modelling the parity function. RNN is an umbrella term that
incorporates vanilla (simple) RNN, Bidirectional RNN (BRNN), Gated Recurrent
Unit (GRU), LSTM and a wide range of their variations like the Memory-
Augmented RNN (MRNN) that enhances RNNs’ ability on handling on sequential
data with long dependencies Zhao et al. (2020). Zhao et al. (2020) argued that
RNN and LSTM are incapable of processing long time series data that requires
persistent memorization, which is a disadvantage to processing long bitstrings
as flipping any single bit alters the parity and a tiny error in the memory
might incur disastrous repercussion. This discovery aligns with the
theoretical results that the longer bitstrings on which the neural networks
are trained, the harder it is for them to learn to model the parity function
Hahn (2020).

The parity of bitstrings is permutation invariant by its nature, as changing
the order of the bits does not affect the parity. RNNs, despite being
dependent on the order of the input, can be regularized towards permutation
invariant. Cohen-Karlik et al. (2020) showed that RNNs with regularization
applied towards permutation invariance can simulate the correct parity
function for the bitstrings whose length is up to 100.

RNN architectures are, in theory, able to simulate any Turing Machine (TM) Al-
Rawi (2005); Siegelmann and Sontag (1995) given the suitable weights and
biases, but the results are predicated on unrealistic assumptions such as
unlimited computation time and infinite precision representation of states. In
practice, finding proper parameters through gradient descent algorithms for
RNNs is a demanding task due to the notoriously hard vanishing gradient
problem Hochreiter and Schmidhuber (1997). With the number of bitstrings
increasing, the difficulty of the RNN modelling the parity function also
escalates drastically.

Self-Attention networks (a.k.a Transformer architectures) Vaswani et al.
(2017) underpin many Natural Language Processing (NLP) applications since its
emergence in 2017. However, Hahn (2020) has shown strong theoretical
limitations of the abilities of the Self-Attention network on evaluating
logical formulas, which is equivalent to evaluating the parity of bitstrings,
and draw a conclusion from asymptotic results that any transformers will make
mistakes on modelling the parity when the input is sufficiently long.

Researchers from DeepMind developed PonderNet Banino et al. (2021) and showed
its ability to model the parity function by adaptive computation where the
computation needed is proportional to the complexity of the problem. The
PonderNet achieved almost perfect accuracy on this hard extrapolation task.
Still, unlike RNNs that can process the input vectors of any length through
unrolling, it can only be evaluated on the same length of the input vectors as
the ones it was trained on. Their experiments were intended to demonstrate the
computational adaptability of the PonderNet using the parity function as a
testbed rather than exhibiting its power in modelling the parity function. But
it shows that as the bitstrings become increasingly complicated, i.e. more 1s
or -1s in the bitstring Abbe et al. (2023), the computational resources
required to learn the parity increases to the extent where when the bitstring
is sufficiently long, the required resources are enormous, if not
unobtainable.

##  3 Learning parity function with noisy labels

Zhou and Riis (2022) implemented an AlphaZero-style algorithm for Nim in which
any board position is represented by a fixed-length list consisting of 0, 1
and -1s. The initial board position where no counters are removed is
represented by a list of 1s and -1s, and the representation of the end
position consists of 0s and -1s. During the game, each move results in some 1s
being replaced by 0s. Thus the collection of game states encountered by the
agent resembles the ones that form a latent curriculum and contains more easy
samples compared with the ones generated from the uniform distribution.

###  3.1 Learning parity function from latent curriculum

Given this observation, our investigation focused on the impact of bitstring
length on neural network performance in modelling the parity function within a
latent curriculum setting. This setting closely mirrors the optimal scenario
in self-play reinforcement learning (RL), where the progression of learning
experiences ideally forms an effective curriculum for the agent. As a single-
layer LSTM model can model a perfect parity function, we used it as our model.
The model was optimized under binary cross entropy (BCE) loss with mini-batch
SGD with size 128. The maximum number of training steps in each experiment is
7.5 million. Our experiments tested bitstrings whose length spans from 20 to
100. We repeated each of the experiments with 10 different random seeds. Under
each experiment, the model is considered to have simulated a parity function
if its accuracy on test data exceeds 95 per cent. An experiment is
conceptually considered successful if the model models the parity function. We
will refer to this definition later when presenting the results.

Figure 1 summarises the results of these experiments. Figure 1(a) demonstrates
the number of experiments out of 10 in which the model succeeded in modelling
a parity function. It is salient that as the length of the bitstring expands,
more experiments fail as the longer bitstrings introduce more variance to the
latent curriculum.

Figure 1(b) describes the relationship between the length of bitstrings and
the number of training steps the model needed to model the parity function if
they succeeded, along with their sensitivity to the nuances of the sampled
data under different seeds measured by the difference among the numbers of
training steps for a given bitstring length. Considering that in the failed
experiments where the number of training steps exceeded 7.5 million, we can
conclude that the model is more sensitive to the subtleties of the
distribution from which the bitstrings are sampled as their length grows, and
additionally, the model tends to need more training steps on longer
bitstrings.

(a) The number of experiments in which the LSTM succeeded in modelling the
parity function in 7.5 million training steps.

(b) The number of training steps needed for the LSTM model to model the parity
function from bitstrings of lengths ranging from 20 to 100.

Figure 1: Under the dataset generated by the latent curriculum, 10 experiments
with 10 random seeds were conducted for each given bitstring length.

Our results align with the results from Daniely and Malach (2020) that showed
on bitstrings sampled from normal distribution, neural networks on longer
bitstrings require more training steps to converge. While the training process
with the bitstrings constituting a latent curriculum differs from the CL where
only spare samples are presented at the early stage of training as each batch
of samples fitting into the NN consists of both spare and dense samples, our
results on the latent curriculum can be extended to a CL setting that mirrors
the way the data samples are presented to NNs in a self-play RL algorithm.

###  3.2 Learning parity function from latent curriculum with noisy labels

We showed in Section 1 that in AlphaZero-style training for two-player games,
the label of the states arising in the play is determined by the outcome of
the games, meaning that the label for the training samples is subject to
change and is likely to be inaccurate, especially in the early stage of the
training. This counteracts the profits of curriculum learning in which simple
samples are presented to facilitate learning in the early training stage.

We considered an ideal self-play RL setting in which the states an agent acts
in establish a latent curriculum, enabling the neural networks in RL to learn
a parity function and the noisy label problem is the only problem that could
affect the ability of a neural network to model a parity function. To simulate
this setting, we propose a new binary classification task in which the data
distribution provides a latent curriculum learnable by neural networks via
gradient descent methods and the portion of noisy labels is in inverse
proportion to the model accuracy. Concretely, the dataset $\mathcal{D}_{t}$
used at each of the training epochs consists of $\rho$ per cent of data with
incorrect noisy labels ($\mathcal{D}_{nl}$), and the rest have correct labels
($\mathcal{D}_{cl}$), as formulated below.

$\mathcal{D}_{t}=\rho\mathcal{D}_{nl}+(1-\rho)\mathcal{D}_{cl}$ (5)

The proportion of noisy labels decreases linearly as the model accuracy
increases. Their relationship can be described by the equation below.

$\rho=\begin{cases}\rho_{0}&x\leq 0.5\\\ 2\rho_{0}(1-x)&\mathrm{otherwise}\\\
\end{cases}$ (6)

where $\rho_{0}$ represents the percentage of mislabeled data before the
training begins, mimicking the noise brought by an untrained model in
AlphaZero-style algorithms. This setting enforces that the proportion of noisy
data in the dataset decreases linearly from an initial percentage of
$\rho_{0}$ to zero as the model’s accuracy on the dataset increases from the
initial roughly 50 per cent at the onset of the training to 100 per cent where
the neural network models perfect parity function.

We extend our experiments on latent curriculum learning to further test the
impact of the noisy labels on the ability of the model to model parity
function. As shown in Figure 2, it is obvious that the model is more
susceptible to these mislabels on longer bitstrings. In our setting, the model
is immune to mislabels accounting for 45 per cent of the data on the
bitstrings of length 20, while more than 5 per cent of wrong labels on
bitstrings of length 100 can hinder the capability of the model to simulate a
parity function.

Figure 2: The maximum percentage of the noisy labels in the dataset on which
the LSTM model can model the parity function with more than 95% accuracy
across bitstrings whose length ranges from 20 to 100.

In this simulated ideal self-play RL setting, the noisy labels on long
bitstring adversely impact the ability of the neural network to model a parity
function. This indicates that in a real self-play RL setting where the states
the agent learns from do not establish a hidden curriculum, this problem is
exacerbated and leads to more difficulty. This observation is consistent with
the findings reported in Zhou and Riis (2022), where the performance of a
self-play AlphaZero algorithm tailored for Nim notably diminishes as the size
of the nim board increases.

##  4 Conclusion

In this paper, we first illustrated the essential role of a parity function in
determining the winning strategy for impartial games and summarised the
results of recent studies on the intricacy of learning a parity function with
neural networks. These challenges naturally apply to self-play reinforcement
learning algorithms that use neural networks on impartial games.

We further identified the noisy label problem that could pose another
challenge. It would be desirable to investigate how the noisy label problem
affects the performance of an agent in an actual self-play RL setting, but due
to the multitude of factors impacting its performance, such as the randomness
in the RL system and their sensitivity to the choice of hyper-parameters, we
instead propose a scenario where except noisy labels all other factors are
ruled out. Our main work focused on identifying and analysing the detrimental
effect brought by the noisy labels on neural networks learning a parity
function from long bitstrings that constitute a latent curriculum, simulating
an ideal self-play reinforcement learning setting where noisy labels diminish
as the increasing model accuracy. Our findings contribute to the studies
investigating the challenges facing self-play RL algorithms on impartial
games.

## Acknowledgment

This work was funded by the Chinese Scholarship Council (CSC). We appreciate
the assistance of the IT Research team at the University of Queen Mary for
supporting us in using the Apocrita HPC facility.

## References

  * Abbe et al. [2023] Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi.  Provable advantage of curriculum learning on parity targets with mixed inputs.  _arXiv preprint arXiv:2306.16921_ , 2023.
  * Al-Rawi [2005] Mohammed Al-Rawi.  A neural network to solve the hybrid n-parity: Learning with generalization issues.  _Neurocomputing_ , 68:273–280, 2005.
  * Banino et al. [2021] Andrea Banino, Jan Balaguer, and Charles Blundell.  Pondernet: Learning to ponder.  _arXiv preprint arXiv:2107.05407_ , 2021.
  * Berlekamp et al. [2001] Elwyn R Berlekamp, John H Conway, and Richard K Guy.  _Winning ways for your mathematical plays, volume 1_.  AK Peters/CRC Press, 2001.
  * Bylander [1994] Tom Bylander.  Learning linear threshold functions in the presence of classification noise.  In _Proceedings of the seventh annual conference on Computational learning theory_ , pages 340–347, 1994.
  * Cohen-Karlik et al. [2020] Edo Cohen-Karlik, Avichai Ben David, and Amir Globerson.  Regularizing towards permutation invariance in recurrent models.  _arXiv preprint arXiv:2010.13055_ , 2020.
  * Cornacchia and Mossel [2023] Elisabetta Cornacchia and Elchanan Mossel.  A mathematical model for curriculum learning for parities.  2023\.
  * Daniely and Malach [2020] Amit Daniely and Eran Malach.  Learning parities with neural networks.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Everitt et al. [2017] Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus Hutter, and Shane Legg.  Reinforcement learning with a corrupted reward channel.  _arXiv preprint arXiv:1705.08417_ , 2017.
  * Franco and Cannas [2001] Leonardo Franco and Sergio A Cannas.  Generalization properties of modular networks: implementing the parity function.  _IEEE transactions on neural networks_ , 12(6):1306–1313, 2001.
  * Hahn [2020] Michael Hahn.  Theoretical limitations of self-attention in neural sequence models.  _Transactions of the Association for Computational Linguistics_ , 8:156–171, 2020.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hohil et al. [1999] Myron E Hohil, Derong Liu, and Stanley H Smith.  Solving the n-bit parity problem using neural networks.  _Neural Networks_ , 12(9):1321–1323, 1999.
  * Liu et al. [2002] Derong Liu, Myron E Hohil, and Stanley H Smith.  N-bit parity neural networks: new solutions based on linear programming.  _Neurocomputing_ , 48(1-4):477–488, 2002.
  * Liu and Guo [2020] Yang Liu and Hongyi Guo.  Peer loss functions: Learning from noisy labels without knowing noise rates.  In _International conference on machine learning_ , pages 6226–6236. PMLR, 2020.
  * Natarajan et al. [2013] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari.  Learning with noisy labels.  _Advances in neural information processing systems_ , 26, 2013.
  * Nick [2014] Bostrom Nick.  Superintelligence: Paths, dangers, strategies.  2014\.
  * Scott [2015] Clayton Scott.  A rate of convergence for mixture proportion estimation, with application to learning from noisy labels.  In _Artificial Intelligence and Statistics_ , pages 838–846. PMLR, 2015.
  * Scott et al. [2013] Clayton Scott, Gilles Blanchard, and Gregory Handy.  Classification with asymmetric label noise: Consistency and maximal denoising.  In _Conference on learning theory_ , pages 489–511. PMLR, 2013.
  * Shalev-Shwartz et al. [2017] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah.  Failures of gradient-based deep learning.  In _International Conference on Machine Learning_ , pages 3067–3075. PMLR, 2017.
  * Siegelmann and Sontag [1995] Hava T Siegelmann and Eduardo D Sontag.  On the computational power of neural nets.  _Journal of computer and system sciences_ , 50(1):132–150, 1995.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Song et al. [2022] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee.  Learning from noisy labels with deep neural networks: A survey.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2022.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, 2017.
  * Wang et al. [2020] Jingkang Wang, Yang Liu, and Bo Li.  Reinforcement learning with perturbed rewards.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 6202–6209, 2020.
  * Wilamowski et al. [2003] Bodgan M Wilamowski, David Hunter, and Aleksander Malinowski.  Solving parity-n problems with feedforward neural networks.  In _Proceedings of the International Joint Conference on Neural Networks, 2003._ , volume 4, pages 2546–2551. IEEE, 2003.
  * Zhao et al. [2020] Jingyu Zhao, Feiqing Huang, Jia Lv, Yanjie Duan, Zhen Qin, Guodong Li, and Guangjian Tian.  Do rnn and lstm have long memory?  In _International Conference on Machine Learning_ , pages 11365–11375. PMLR, 2020.
  * Zhou and Riis [2022] Bei Zhou and Søren Riis.  Impartial games: A challenge for reinforcement learning.  _arXiv preprint arXiv:2205.12787_ , 2022.