11institutetext: Department of Computer Science and Engineering,
22institutetext: Department of Chemical and Biological Engineering,
The Hong Kong University of Science and Technology, Hong Kong, China
22email<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>22email:
<EMAIL_ADDRESS>
# Scale Federated Learning for Label Set Mismatch in Medical Image
Classification

Zhipeng Deng 11 Luyang Luo 11 Hao Chen 1122

###### Abstract

Federated learning (FL) has been introduced to the healthcare domain as a
decentralized learning paradigm that allows multiple parties to train a model
collaboratively without privacy leakage. However, most previous studies have
assumed that every client holds an identical label set. In reality, medical
specialists tend to annotate only diseases within their area of expertise or
interest. This implies that label sets in each client can be different and
even disjoint. In this paper, we propose the framework FedLSM to solve the
problem of Label Set Mismatch. FedLSM adopts different training strategies on
data with different uncertainty levels to efficiently utilize unlabeled or
partially labeled data as well as class-wise adaptive aggregation in the
classification layer to avoid inaccurate aggregation when clients have missing
labels. We evaluated FedLSM on two public real-world medical image datasets,
including chest X-ray (CXR) diagnosis with 112,120 CXR images and skin lesion
diagnosis with 10,015 dermoscopy images, and showed that it significantly
outperformed other state-of-the-art FL algorithms. The code can be found at
https://github.com/dzp2095/FedLSM.

###### Keywords:

Federated Learning Label Set Mismatch

##  1 Introduction

Federated learning (FL) [15] is an emerging decentralized learning paradigm
that enables multiple parties to collaboratively train a model without sharing
private data. FL was initially developed for edge devices, and it has been
extended to medical image analysis to protect clinical data [2, 6, 12, 21].
Non-identically independently distributed (Non-IID) data among clients is one
of the most frequently stated problems with FL [5, 7, 8, 9]. However, most
studies of non-IID FL assumed that each client owns an identical label set,
which does not reflect real-world scenarios where classes of interest could
vary among clients. In the medical field, for instance, datasets from
different centers (_e.g._ , hospitals) are generally annotated based on their
respective domains or interests. As a result, the label sets of different
centers can be non-identical, which we refer to as label set mismatch.

To this end, we propose to solve this challenging yet common scenario where
each client holds different or even disjoint annotated label sets. We consider
not only single-label classification but also multi-label classification where
partial labels exist, making this problem setting more general and
challenging. Specifically, each client has data of locally identified classes
and locally unknown classes. Although locally identified classes differ among
clients, the union of identified classes in all clients covers locally unknown
classes in each client.

Figure 1: Illustration of the Label Set Mismatch problem. Each node (client)
has its own identified class set, which can differ from other nodes. The label
in the box represents the correct complete label, while the label in the red
text represents the partial label actually assigned to the image.

There are few studies directly related to the label set mismatch scenario. The
previous attempts were either limited in scope or have not achieved
satisfactory results. For instance, FedRS [10] assumed that each client only
owns locally identified classes. FedPU [11] assumed that each client owns
labels of locally identified classes and unlabeled data of all classes but it
was not applicable to multi-label classification. FPSL [2] was designed for
federated partially supervised learning which only targets multi-label
classification. Over and above that, FedRS and FedPU tried to solve this
problem only through local updating and ignored the server aggregation process
in FL, leading to unsatisfactory performance. FPSL used bi-level optimization
in the local training, which is only effective when the data is very limited.
Federated semi-supervised learning (FedSemi) [1, 4, 6, 12, 22] is another
related field, but almost all of them assumed that some annotated clients [1,
4, 12] or a server [6, 4, 22] own labels of all classes. However, in real-
world scenarios, especially in the healthcare domain, each client may only
annotate data of specific classes within their domains and interests.

In this paper, we present FedLSM, a framework that aims to solve Label Set
Mismatch and is designed for both single-label and multi-label classification
tasks. FedLSM relies on pseudo labeling on unlabeled or partially labeled
samples, but pseudo labeling methods could lead to incorrect pseudo labels and
ignorance of samples with relatively lower confidence. To address these
issues, we evaluate the uncertainty of each sample using entropy and conduct
pseudo labeling only on data with relatively lower uncertainty. We also apply
MixUp[23] between data with low and high uncertainty and propose an adaptive
weighted averaging for the classification layer that considers the client
class-wise data numbers. We validated our propose method on two real-world
tasks, including Chest X-ray (CXR) [14, 13] diagnosis (multi-label
classification) and skin lesion diagnosis [1] (single-label classification).
Extensive experiments demonstrate that our method outperforms a number of
state-of-the-art FL methods, holding promise in tackling the label set
mismatch problem under federated learning.

##  2 Methodology

###  2.1 Problem Setting

Figure 2: Overview of the FedLSM framework. (a) Client training details,
including uncertainty estimation (UE) and different training strategies for
data with different uncertainty levels. The estimated disease distribution
(EDD) is calculated using existing labels and pseudo labels. (b) Overview of
the proposed scenario and FL paradigm, where each client has non-identical
missing labels. EDD represents each client’s contribution to each proxy in the
adaptive classification layer aggregation.

We followed the common FL scenario, where there are _K_ clients and one
central server. Each client owns a locally-identified class set
$\mathcal{I}_{k}$ and a locally-unknown class set $\mathcal{U}_{k}$. Although
$\mathcal{I}_{k}$ and $\mathcal{U}_{k}$ can vary among clients and may even be
disjoint, all clients share an identical class set as:

$\mathcal{C}=\mathcal{I}_{k}\cup\mathcal{U}_{k},\ k=1,\ 2,\ ...,\ K.$ (1)

Despite the fact that each client only identifies a subset of the class set
$\mathcal{C}$, the union of locally identified class sets equals
$\mathcal{C}$, which can be formulated as:

$\mathcal{C}=\mathcal{I}_{1}\cup\mathcal{I}_{2}\ ...\ \cup\mathcal{I}_{K}.$
(2)

The local dataset of client $\mathit{k}$ is denoted as
$\mathcal{D}_{k}=\\{(x^{i},y^{i})\\}_{i=1}^{n_{k}}$, where $n_{k}$ denotes the
number of data, $x_{i}$ is the $\mathit{i}$-th input image, and
$y^{i}=[y^{i}_{1},\ ...,\ y^{i}_{c},\ ...,\ y^{i}_{M}]$ is the $\mathit{i}$-th
label vector, M is the number of classes in $\mathcal{C}$ and $y^{i}_{c}$
refers to the label of class $\mathit{c}$. Notably, if $c\in\mathcal{I}_{k}$,
$y^{i}_{c}\in\\{0,1\\}$. If $c\in\mathcal{U}_{k}$, $y^{i}_{c}$ is set to 0.

For subsequent illustration, we denote the backbone model as
$f(\cdot)=f_{\Psi}(f_{\theta}(\cdot))$, where $f_{\theta}(\cdot)$ refers to
the feature extractor with parameters $\theta$ and $f_{\Psi}$ refers to the
last classification layer with parameters $\Psi=\\{{\psi_{c}}\\}_{c=1}^{M}$.
Adopting the terminology from previous studies [10, 17], we refer to $\Psi$ as
_proxies_ and $\psi_{c}$ as _c_ -th _proxy_.

###  2.2 Overview of FedLSM

Our proposed framework is presented in Fig. 2. As depicted in Fig. 2 (a), we
evaluate the uncertainty of each sample in the local dataset $\mathcal{D}_{k}$
using the global model $f(\cdot)$ and split it into three subsets based on the
uncertainty level. The low and medium uncertainty subsets are used for pseudo
labeling-based training, while the low and high uncertainty subsets are
combined by MixUp [23] to efficiently utilize uncertain data that might be
ignored in pseudo labeling. The estimated disease distribution $q^{k}_{c}$ on
client $k$ is calculated using the existing labels and pseudo labels. After
local training, each client sends its estimated disease distribution $q^{k}$
and model weight $f_{k}(\cdot)$ to the central server. The feature extractors
$\Theta$ are aggregated using FedAvg [15] while proxies $\Psi$ are aggregated
using our proposed adaptive weighted averaging with the help of $q^{k}$.

###  2.3 Local Model Training

Uncertainty Estimation (UE). We use the global model to evaluate the
uncertainty of each sample in the local dataset by calculating its entropy
[16]. The calculation of entropy in single-label classification is defined as:

$H(x^{i})=-\sum_{c}{P(y=c|x^{i})log(P(y=c|x^{i}))}$ (3)

where $P(y=c|x^{i})$ refers to the predicted probability for a given class c
and input $x^{i}$. The calculation of entropy in multi-label classification is
similar to single-label classification where we only consider
$\mathcal{U}_{k}$ and normalize the result to [0, 1]. After calculating the
entropy, we empirically determine $n_{k}^{h}$ and $n_{k}^{l}$ and group the
data with top-$n_{k}^{h}$ highest entropy as uncertain dataset
$\mathcal{D}_{k}^{h}$, top-$n_{k}^{l}$ lowest entropy as confident dataset
$\mathcal{D}_{k}^{l}$, and the rest as $\mathcal{D}_{k}^{m}$.

Pseudo Labeling. After local models are trained and aggregated on the central
server, the resulting global model can identify the entire class set
$\mathcal{C}$. Thereafter, we can use pseudo labeling-based method to leverage
partially labeled or unlabeled data in
$\mathcal{D}_{k}^{l}\cup\mathcal{D}_{k}^{m}$. We use the weakly-augmented
version (i.e., slightly modified via rotations, shifts, or flips) of $x^{i}$
to generate pseudo labels on locally unknown classes by the teacher model. The
loss $\mathcal{L}_{\mathcal{I}_{k}}$ applied on locally identified class set
$\mathcal{I}_{k}$ is cross-entropy, and the loss applied on the locally
unknown class set $\mathcal{U}_{k}$ of _k_ -th client in single-label
classification can be formulated as:

$\mathcal{L}_{\mathcal{U}_{k}}=-\frac{1}{N_{\mathcal{U}_{k}}}\sum_{i=1}^{N_{\mathcal{U}_{k}}}\sum_{c\in\mathcal{U}_{k}}\mathbbm{1}(f_{g,c}(\alpha(x^{i}))\geq\tau){\hat{y}_{c}^{i}\mathrm{log}f_{k,c}(\mathcal{A}(x)^{i})}$
(4)

where $N_{\mathcal{U}_{k}}$ denotes the number of unlabeled data,
$f_{k,c}(\cdot)$ is the predicted probability for class $\mathit{c}$ of the
student model on _k_ -th client, $\alpha(\cdot)$ and $\mathcal{A}(\cdot)$
refer to weak and strong augmentation respectively, $f_{g,c}(\alpha(x^{i}))$
is the predicted probability of class _c_ on the weakly augmented version of
$x^{i}$ by the teacher model,
$\hat{y}^{i}=\mathrm{argmax}(f_{g,c}(\alpha(x^{i}))$ is the pseudo label and
$\tau$ is the threshold used to filter unconfident pseudo label. Specifically,
the teacher model and student model both are initialized from the global
model, while the teacher model is updated using exponential moving average
(EMA) with the weights of the student model during training. Likewise, the
loss function $\mathcal{L}_{\mathcal{I}_{k}}$ in multi-label classification is
binary cross entropy and $\mathcal{L}_{\mathcal{U}_{k}}$ is:

$\begin{split}\mathcal{L}_{\mathcal{U}_{k}}=&-\frac{1}{N_{\mathcal{C}}}\sum_{i=1}^{N_{\mathcal{C}}}\sum_{c\in\mathcal{U}_{k}}[\mathbbm{1}(f_{g,c}(\alpha(x^{i}))\geq\tau_{p})\hat{y}^{i}_{c}\mathrm{log}(f_{k,c}(\mathcal{A}(x^{i})))\\\
&+\mathbbm{1}(f_{g,c}(\alpha(x^{i}))\leq\tau_{n})(1-\hat{y}^{i}_{c})\mathrm{log}(1-f_{k,c}(\mathcal{A}(x^{i})))]\end{split}$
(5)

where $\tau_{p}$ and $\tau_{n}$ are the confidence threshold for positive and
negative labels, $N_{\mathcal{C}}$ is the number of data.

Uncertain Data Enhancing (UDE). The pseudo label filtering mechanism makes it
difficult to acquire pseudo-labels for uncertain data, which results in their
inability to contribute to the training process. To overcome this limitation,
we propose to MixUp [23] dataset with lowest entropy (confident)
$\mathcal{D}_{k}^{l}$ and dataset with highest entropy as (uncertain)
$\mathcal{D}_{k}^{h}$ to generate softer label $\tilde{y}$ and input
$\tilde{x}$ as

$\begin{split}\tilde{x}=&\lambda x_{l}+(1-\lambda)x_{h}\\\ \tilde{y}=&\lambda
y_{l}+(1-\lambda)y_{h}\end{split}$ (6)

, where $x_{l}\in\mathcal{D}_{k}^{l}$ and $x_{h}\in\mathcal{D}_{k}^{h}$, and
$y_{l}$ and $y_{h}$ are their corresponding labels or pseudo labels,
respectively. We generate pseudo labels for uncertain data $(x_{h},y_{h})$
with a relatively smaller confidence threshold. The UDE loss function
$\mathcal{L}_{UDE}$ is cross-entropy loss.

Overall loss function. The complete loss function is defined as:
$\mathcal{L}=\mathcal{L}_{\mathcal{I}_{k}}+\mathcal{L}_{\mathcal{U}_{k}}+\lambda\mathcal{L}_{UDE}$,
where $\lambda$ is a hyperparameter to balance different objectives.

###  2.4 Server Model Aggregation

After local training, the server will collect all the client models and
aggregate them into a global model. In the _r_ -th round, the aggregation of
the feature extractors $\\{\theta_{k}\\}_{k=1}^{K}$ is given by:
$\theta^{r+1}\leftarrow\sum_{k}^{K}{\frac{n_{k}}{n}\theta_{k}^{r}}$, where
$n=\sum_{k}^{K}n_{k}$.

Adaptive weighted proxy aggregation (AWPA). As analyzed in [10], due to the
missing labels of locally unknown class set $\mathcal{U}_{k}$ on _k_ -th
client, the corresponding proxies $\\{{\psi_{k,c}}\\}_{c\in\mathcal{U}_{k}}$
are inaccurate and will further cause error accumulation during model
aggregation. FedRS [10] and FedPU [11] both seek to solve this problem only
through local training while we use pseudo labels and the existing labels to
indicate the contribution of aggregation of proxies as:

$\psi_{c}^{r+1}\leftarrow\sum_{k=1}^{K}\frac{q_{c}^{k}}{\sum_{j=1}^{K}q_{c}^{j}}{\psi^{r}_{k,c}}$
(7)

where $q_{c}^{k}$ refers to the number of training data of the _c_ -th class
on the _k_ -th client. During training, if $c\in\mathcal{U}_{k}$, $q_{c}^{k}$
is estimated by the number of pseudo labels as
$q_{c}^{k}=\sum_{i=1}^{n_{k}}\hat{y}^{i}_{c}$. The weighting number of each
client is modulated in an adaptive way through the pseudo labeling process in
each round.

##  3 Experiments

###  3.1 Datasets

We evaluated our method on two real-world medical image classification tasks,
including the CXR diagnosis (multi-label) and skin lesion diagnosis (single-
label).

Task 1) NIH CXR diagnosis. We conducted CXR diagnosis with NIH ChestX-ray14
dataset [20], which contains 112,120 frontal-view CXR images from 32,717
patients. NIH CXR diagnosis is a multi-label classification task and each
image is annotated with 14 possible abnormalities (positive or negative).

Task 2) ISIC2018 skin lesion diagnosis. We conducted skin lesion diagnosis
with HAM10000 [19], which contains 10,015 dermoscopy images. ISIC2018 skin
lesion diagnosis is a single-label multi-class classification task where seven
exclusive skin lesion sub-types are considered.

Training, validation and testing sets for both datasets were divided into
7:1:2.

###  3.2 Experiment Setup

FL setting. We randomly divided the training set into _k_ client training sets
and randomly select _s_ classes as locally identified classes on each client.
We set the number of clients $k=8$, the number of classes $s=3$ for Task 1 and
$k=5,s=3$ for Task 2. Please find the detail of the datasets in the
supplementary materials.

Table 1: Comparison with state-of-the-art methods on NIH CXR diagnosis.
(a) FedAvg with 100% labeled data (b) FedAvg [15] (c) FedAvg* [15] (d) FedProx* [8] (e) MOON* [7] (f) FedRS [10] (g) FPSL [2] (h) FedAvg-FixMatch* [18] (i) FSSL* [22]. * denotes the use of task-dependent model aggregation in FPSL[2]. Disease Methods | (a) | (b) | (c) | (d) | (e) | (f) | (g) | (h) | (i) | Ours
---|---|---|---|---|---|---|---|---|---|---
Consolidation | 0.750 | 0.682 | 0.724 | 0.716 | 0.718 | 0.685 | 0.709 | 0.730 | 0.713 | 0.727
Pneumonia | 0.717 | 0.695 | 0.684 | 0.707 | 0.700 | 0.685 | 0.711 | 0.699 | 0.706 | 0.700
Effusion | 0.828 | 0.710 | 0.750 | 0.766 | 0.760 | 0.732 | 0.773 | 0.800 | 0.759 | 0.804
Emphysema | 0.913 | 0.717 | 0.842 | 0.842 | 0.877 | 0.644 | 0.837 | 0.813 | 0.705 | 0.901
Edema | 0.849 | 0.765 | 0.814 | 0.811 | 0.817 | 0.756 | 0.813 | 0.815 | 0.805 | 0.833
Atelectasis | 0.776 | 0.634 | 0.721 | 0.716 | 0.722 | 0.660 | 0.712 | 0.741 | 0.682 | 0.757
Nodule | 0.768 | 0.707 | 0.722 | 0.729 | 0.720 | 0.685 | 0.716 | 0.735 | 0.695 | 0.742
Mass | 0.820 | 0.686 | 0.725 | 0.723 | 0.736 | 0.670 | 0.704 | 0.767 | 0.682 | 0.775
Thickening | 0.775 | 0.726 | 0.732 | 0.737 | 0.740 | 0.720 | 0.725 | 0.745 | 0.726 | 0.755
Cardiomegaly | 0.877 | 0.750 | 0.830 | 0.840 | 0.841 | 0.707 | 0.820 | 0.858 | 0.794 | 0.846
Fibrosis | 0.817 | 0.760 | 0.766 | 0.772 | 0.780 | 0.750 | 0.775 | 0.776 | 0.790 | 0.804
Hernia | 0.850 | 0.623 | 0.840 | 0.886 | 0.873 | 0.609 | 0.870 | 0.865 | 0.837 | 0.884
Pneumothorax | 0.865 | 0.790 | 0.818 | 0.805 | 0.836 | 0.761 | 0.809 | 0.836 | 0.766 | 0.858
Infiltration | 0.696 | 0.695 | 0.687 | 0.678 | 0.689 | 0.682 | 0.672 | 0.680 | 0.700 | 0.680
Average AUC | 0.807 | 0.710 | 0.760 | 0.766 | 0.772 | 0.697 | 0.760 | 0.776 | 0.740 | 0.791

Data augmentation and preprocessing. The images in Task 1 were resized to
320$\times$320, while in Task 2, they were resized to 224$\times$224\. For all
experiments, weak augmentation refered to horizontal flip, and strong
augmentation included a combination of random flip, rotation, translation,
scaling and one of the blur transformations in gaussian blur, gaussian noise
and median blur.

Evaluation Metrics. For Task 1, we adopted AUC to evaluate the performance of
each disease. For task 2, we reported macro average of AUC, Accuracy, F1,
Precision and Recall of each disease. All the results are averaged over 3
runs.

Implementation Details. We used DenseNet121[3] as the backbone for all the
tasks. The network was optimized by Adam optimizer where the momentum terms
were set to 0.9 and 0.99. The total batch size was 64 with 4 generated samples
using UDE. In task 1, we used the weighted binary cross-entropy as in FPSL[2].
The local training iterations were 200 and 30 for Task 1 and Task 2,
respectively, while the total communication rounds were 50 for both tasks.
Please find more detailed hyperparameter settings in the supplementary
material.

Table 2: Comparison with state-of-the-art methods on ISIC2018 Skin Lesion diagnosis.* denotes the use of task-dependent model aggregation in FPSL[2]. Methods | AUC | Accuracy | F1 | Precision | Recall
---|---|---|---|---|---
| FedAvg with 100% labeled data
---
0.977 | 0.889 | 0.809 | 0.743 | 0.800
FedAvg [15] | 0.927 | 0.810 | 0.576 | 0.721 | 0.622
FedAvg* [15] | 0.949 | 0.817 | 0.620 | 0.753 | 0.597
FedProx* [8] | 0.952 | 0.820 | 0.630 | 0.768 | 0.612
MOON* [7] | 0.948 | 0.826 | 0.652 | 0.755 | 0.620
FedPU [11] | 0.927 | 0.796 | 0.550 | 0.699 | 0.570
FedRS [10] | 0.926 | 0.800 | 0.577 | 0.716 | 0.597
FPSL [2] | 0.952 | 0.825 | 0.638 | 0.728 | 0.613
FedAvg* + FixMatch [18] | 0.940 | 0.789 | 0.564 | 0.681 | 0.541
FSSL* [22] | 0.939 | 0.807 | 0.608 | 0.740 | 0.580
Ours | 0.960 | 0.846 | 0.713 | 0.763 | 0.699
Table 3: Ablation studies in terms of major components on task 1 and task 2.* denotes the use of masked aggregation of proxies. Method | Task 1 | Task 2
---|---|---
AUC | AUC | Accuracy | F1 | Precision | Recall
Ours* w/o AWPA | 0.784 | 0.950 | 0.837 | 0.676 | 0.783 | 0.646
Ours w/o UDE | 0.689 | 0.954 | 0.825 | 0.655 | 0.774 | 0.638
Ours w/o UE | 0.705 | 0.951 | 0.832 | 0.660 | 0.697 | 0.646
Ours | 0.791 | 0.960 | 0.846 | 0.713 | 0.763 | 0.699

###  3.3 Comparison with state-of-the-arts and ablation study

We compared our method with recent state-of-the-art (SOTA) non-IID FL methods,
including FedProx [8], which applied $L_{2}$ regularization, and MOON [7],
which introduced contrastive learning. We also compared with other SOTA non-
IID FL methods that shared a similar setting with ours, including FedRS [10],
which restricted proxy updates of missing classes, FedPU [11], which added a
misclassification loss, and FPSL [2], which adopted task-dependent model
aggregation. Additionally, we compared with FedSemi methods that can be easily
translated into the label set mismatch scenario including FSSL [22] and FedAvg
with FixMatch [18]. For our evaluation, we used FedAvg with 100% labeled data
as the benchmark and FedAvg trained with the same setting as the lower bound.

The quantitative results for the two tasks are presented in Table 1 and Table
6. To ensure a fair comparison, we adopted the task-dependent model
aggregation proposed in FPSL [2] in most of the compared FL methods, with the
exception of FedRS and FedPU which are specifically designed for the similar
scenario with us. Our proposed FedLSM achieves the best performance on almost
all metrics. Notably, the improvement over the second-best method is 1.5% for
average AUC on Task 1 and 6.1% for F1-score on Task 2.

Ablation study. We conducted ablation studies to assess the effectiveness of
the primary components of our FedLSM framework. As depicted in Table 3, the
performance drops significantly without UE or UDE. On the other hand, the
adoption of AWPA boosts the performance by 0.7% in AUC for Task 1, 3.7% in
F1-score, and 5.3% in recall for Task 2.

##  4 Conclusion

We present an effective framework FedLSM to tackle the issue of label set
mismatch in FL. To alleviate the impact of missing labels, we leverage
uncertainty estimation to partition the data into distinct uncertainty levels.
Then, we apply pseudo labeling to confident data and uncertain data enhancing
to uncertain data. In the server aggregation phase, we use adaptive weighted
proxies averaging on the classification layer, where averaging weights are
dynamically adjusted every round. Our FedLSM demonstrates notable
effectiveness in both CXR diagnosis (multilabel classification) and ISIC2018
skin lesion diagnosis (single-label classification) tasks, holding promise in
tackling the label set mismatch problem under federated learning.

####  4.0.1 Acknowledgement

This work was supported by the Hong Kong Innovation and Technology Fund
(Project No. ITS/028/21FP) and Shenzhen Science and Technology Innovation
Committee Fund (Project No. SGDX20210823103201011).

## References

  * [1] Bdair, T., Navab, N., Albarqouni, S.: Fedperl: semi-supervised peer learning for skin lesion classification. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part III. pp. 336–346. Springer (2021)
  * [2] Dong, N., Kampffmeyer, M., Voiculescu, I., Xing, E.: Federated partially supervised learning with limited decentralized medical images. IEEE Transactions on Medical Imaging (2022)
  * [3] Huang, G., Liu, Z., Van Der Maaten, L., Weinberger, K.Q.: Densely connected convolutional networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 4700–4708 (2017)
  * [4] Jeong, W., Yoon, J., Yang, E., Hwang, S.J.: Federated semi-supervised learning with inter-client consistency & disjoint learning. arXiv preprint arXiv:2006.12097 (2020)
  * [5] Jiang, M., Wang, Z., Dou, Q.: Harmofl: Harmonizing local and global drifts in federated learning on heterogeneous medical images. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 1087–1095 (2022)
  * [6] Jiang, M., Yang, H., Li, X., Liu, Q., Heng, P.A., Dou, Q.: Dynamic bank learning for semi-supervised federated image diagnosis with class imbalance. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2022: 25th International Conference, Singapore, September 18–22, 2022, Proceedings, Part III. pp. 196–206. Springer (2022)
  * [7] Li, Q., He, B., Song, D.: Model-contrastive federated learning. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 10713–10722 (2021)
  * [8] Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A., Smith, V.: Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems 2, 429–450 (2020)
  * [9] Li, X., Jiang, M., Zhang, X., Kamp, M., Dou, Q.: Fedbn: Federated learning on non-iid features via local batch normalization. arXiv preprint arXiv:2102.07623 (2021)
  * [10] Li, X.C., Zhan, D.C.: Fedrs: Federated learning with restricted softmax for label distribution non-iid data. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 995–1005 (2021)
  * [11] Lin, X., Chen, H., Xu, Y., Xu, C., Gui, X., Deng, Y., Wang, Y.: Federated learning with positive and unlabeled data. In: International Conference on Machine Learning. pp. 13344–13355. PMLR (2022)
  * [12] Liu, Q., Yang, H., Dou, Q., Heng, P.A.: Federated semi-supervised medical image classification via inter-client relation matching. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part III 24. pp. 325–335. Springer (2021)
  * [13] Luo, L., Chen, H., Zhou, Y., Lin, H., Pheng, P.A.: Oxnet: omni-supervised thoracic disease detection from chest x-rays. arXiv preprint arXiv:2104.03218 (2021)
  * [14] Luo, L., Yu, L., Chen, H., Liu, Q., Wang, X., Xu, J., Heng, P.A.: Deep mining external imperfect data for chest x-ray disease screening. IEEE transactions on medical imaging 39(11), 3583–3594 (2020)
  * [15] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial intelligence and statistics. pp. 1273–1282. PMLR (2017)
  * [16] Robinson, D.W.: Entropy and uncertainty. Entropy 10(4), 493–506 (2008)
  * [17] Snell, J., Swersky, K., Zemel, R.: Prototypical networks for few-shot learning. Advances in neural information processing systems 30 (2017)
  * [18] Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H., Raffel, C.A., Cubuk, E.D., Kurakin, A., Li, C.L.: Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in neural information processing systems 33, 596–608 (2020)
  * [19] Tschandl, P., Rosendahl, C., Kittler, H.: The ham10000 dataset, a large collection of multi-source dermatoscopic images of common pigmented skin lesions. Scientific data 5(1), 1–9 (2018)
  * [20] Wang, X., Peng, Y., Lu, L., Lu, Z., Bagheri, M., Summers, R.M.: Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 2097–2106 (2017)
  * [21] Xu, A., Li, W., Guo, P., Yang, D., Roth, H.R., Hatamizadeh, A., Zhao, C., Xu, D., Huang, H., Xu, Z.: Closing the generalization gap of cross-silo federated medical image segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 20866–20875 (2022)
  * [22] Yang, D., Xu, Z., Li, W., Myronenko, A., Roth, H.R., Harmon, S., Xu, S., Turkbey, B., Turkbey, E., Wang, X., et al.: Federated semi-supervised learning for covid region segmentation in chest ct using multi-national data from china, italy, japan. Medical image analysis 70, 101992 (2021)
  * [23] Zhang, H., Cisse, M., Dauphin, Y.N., Lopez-Paz, D.: mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412 (2017)

##  5 Supplementary Materials

Table 4: Hyperparameters setting of both tasks. | $\tau$ | $\tau_{l}$ | $\tau_{p}$ | $\tau_{n}$ | $\tau_{lp}$ | $\tau_{ln}$ | $\lambda$ | EMA |  $\alpha$ in MixUp | lr | lr_decay
---|---|---|---|---|---|---|---|---|---|---|---
Task 1 | / | / | 0.85 | $5e^{-3}$ | 0.7 | $1e^{-2}$ | 0.1 | 0.999 | 0.2 | $1e^{-4}$ | $5e^{-4}$
Task 2 | 0.95 | 0.85 | / | / | / | / | 0.1 | 0.999 | 0.2 | $1e^{-4}$ | $5e^{-4}$
Table 5: Task 1 (NIH Chest x-ray diagnosis): Statistics of positive samples among different clients for the experiments that simulate the label set mismatch problem. Each client has 3 locally identified classes and images can be partially labeled. Disease | Devices
---|---
A | B | C | D | E | F | G | H
Consolidation | 309 | 0 | 0 | 0 | 0 | 0 | 0 | 297
Pneumonia | 0 | 88 | 0 | 0 | 0 | 0 | 0 | 0
Effusion | 0 | 0 | 0 | 951 | 0 | 0 | 0 | 0
Emphysema | 0 | 0 | 0 | 0 | 161 | 0 | 0 | 0
Edema | 150 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Atelectasis | 0 | 0 | 0 | 918 | 0 | 0 | 0 | 0
Nodule | 0 | 0 | 0 | 0 | 536 | 505 | 0 | 0
Mass | 0 | 0 | 447 | 0 | 0 | 0 | 0 | 0
Thickening | 0 | 0 | 229 | 0 | 0 | 231 | 0 | 0
Cardiomegaly | 0 | 0 | 0 | 182 | 0 | 0 | 174 | 0
Fibrosis | 0 | 141 | 0 | 0 | 0 | 139 | 0 | 0
Hernia | 0 | 14 | 0 | 0 | 0 | 0 | 20 | 15
Pneumothorax | 271 | 0 | 0 | 0 | 296 | 0 | 0 | 0
Infiltration | 0 | 0 | 1512 | 0 | 0 | 0 | 1469 | 1534
Table 6: Task 2 (ISIC2018 skin lesion diagnosis): Statistics of positive samples among different clients for the experiments that simulate the label set mismatch problem. Each client has 3 locally identified classes. Disease | Devices
---|---
A | B | C | D | E
MEL | 0 | 0 | 156 | 0 | 0
NV | 919 | 915 | 0 | 0 | 0
BCC | 0 | 70 | 80 | 68 | 76
AKIEC | 0 | 0 | 0 | 41 | 41
BKL | 150 | 0 | 0 | 0 | 138
DF | 0 | 16 | 16 | 13 | 0
VASC | 25 | 0 | 0 | 0 | 0


# Rosenblatt’s first theorem and frugality of deep learning

A. N. Kirdin<EMAIL_ADDRESS>S. V. Sidorov<EMAIL_ADDRESS>N. Y. Zolotykh<EMAIL_ADDRESS>Lobachevsky University, Nizhni
Novgorod, Russia  Institute for Computational Modelling, Russian Academy of
Sciences, Siberian Branch, Krasnoyarsk, Russia

###### Abstract

First Rosenblatt’s theorem about omnipotence of shallow networks states that
elementary perceptrons can solve any classification problem if there are no
discrepancies in the training set. Minsky and Papert considered elementary
perceptrons with restrictions on the neural inputs: a bounded number of
connections or a relatively small diameter of the receptive field for each
neuron at the hidden layer. They proved that under these constraints, an
elementary perceptron cannot solve some problems, such as the connectivity of
input images or the parity of pixels in them. In this note, we demonstrated
first Rosenblatt’s theorem at work, showed how an elementary perceptron can
solve a version of the travel maze problem, and analysed the complexity of
that solution. We constructed also a deep network algorithm for the same
problem. It is much more efficient. The shallow network uses an exponentially
large number of neurons on the hidden layer (Rosenblatt’s $A$-elements),
whereas for the deep network the second order polynomial complexity is
sufficient. We demonstrated that for the same complex problem deep network can
be much smaller and reveal a heuristic behind this effect.

###### keywords:

complexity, classification, shallow network, elementary perceptron, deep
network, travel maze problem

##  1 Introduction

Rosenblatt [1] studied elementary perceptrons (Fig. 1). $A$\- and $R$-elements
are the classical linear threshold neurons. The $R$ element is trainable by
the Rosenblatt algorithm, while the $A$-elements should represent a sufficient
collection of features.

Figure 1: Rosenblatt’s elementary perceptron (re-drown from the Rosenblatt
book [1]).

Rosenblatt assumed no restrictions on the choice of the $A$-elements. He
proved that the elementary perceptrons can separate any two non-intersecting
sets of binary images (Rosenblatt’s Theorem 1 in [1]). The proof was very
simple. For each binary image $x$ we can create an $A$-element $A_{x}$ that
produces output 1 for this image and 0 for all other. Indeed, let the input
retina have $n$ elements and $x=(x_{1},\ldots,x_{n})$ be a binary vector
($x_{i}=0$ or 1) with $k$ non-zero elements. The corresponding $A$-element
$A_{x}$ has input synapses with weights $w_{i}=1/k$ if $x_{i}=1$ and
$w_{i}=-1/k$ if $x_{i}=0$. For an arbitrary binary image $y$,

$\sum w_{i}y_{i}\leq 1$

and this sum is equal to $1$ if and only if $y=x$. The threshold for the
$A_{x}$ output can be selected as $1-\frac{1}{2k}$. Thus,

$OutA_{x}(y)=\left\\{\begin{array}[]{ll}0,&if\;\sum
w_{i}y_{i}<1-\frac{1}{2k};\\\ 1,&if\;\sum w_{i}y_{i}\geq
1-\frac{1}{2k}.\end{array}\right.$ (1)

The set of neurons $A_{x}$ created for all binary vectors $x$ transforms
binary images into the vertexes of the standard simplex in
$\mathbb{R}^{2^{n}}$ with coordinates $OutA_{x}(y)$ (1). Any two non-
intersecting subsets of the standard simplex can be separated by a hyperplane.
Therefore, there exists an $R$-element that separates them. According to the
convergence theorem (Rosenblatt’s Theorem 4 in [1]), this $R$-element can be
found by the perceptron learning algorithm (a simple relaxation method for
solving of systems of linear inequalities).

Thus, first Rosenblatt’s theorem is proven:

######  Theorem 1.1.

Elementary perceptron can separate any two non-intersecting sets of binary
images.

Of course, selection of the $A$-elements in the proposed form for all $2^{n}$
binary images is not necessary in the realistic applied classification
problems. Sometimes, even empty hidden layer can be used (the so-called
linearly separable problems). Therefore, together with Rosenblatt’s Theorem 1
we get a problem about reasonable (if not optimal) selection of $A$-element.
There are many frameworks for approaching this question, for example the
general feature selection algorithms: we generate (for example, randomly, or
with some additional heuristics) large set of $A$-elements that is sufficient
for solving classification problem, and then select the appropriate set of
features using different methods. For the bibliography about feature selection
we refer to recent reviews [2, 3, 4].

The Minsky and Papert book ‘‘Perceptron’’ [5] was published seven years later
than Rosenblatt’s book. They started from the restricted percetrons and
assumed that each $A$-element has a bounded receptive field (either by a pre-
selected diameter or by the bounded number of inputs). Immediately, instead of
Rosenblatt’s omnipotence of unrestricted perceptrons, they found that the
elementary perceptron with such restrictions cannot solve some problems like
connectivity of the image or parity of the number of pixels in it. Minsky and
Papert results were generalized to more general metric spaces and graphs [6].
The heuristic behind these results is quite simple: if a human cannot solve
the problem immediately, by a glance, and needs to apply some sequential
operations like counting pixels or following tangled path then this problem is
not solvable by a restricted elementary perceptron.

At the same time, we can expect that the unrestricted elementary perceptron
can solve this problem but for the cost of great (exponential?) complexity.
Multilayer (‘‘deep’’) networks are expected to solve these problems without
explosion of complexity. In that sense, deep networks should be simpler than
shallow networks for the problems that cannot be solved by restricted
elementary perceptrons and require (from humans) combination of parallel and
sequential actions.

In this note, we demonstrate the relative simplicity of deep solvers on a
version of the well-known travel maze problem (Fig. 2). This geometric problem
is closely related to the connectivity problem and has been used for
benchmarking in various areas of machine learning (see, for example, [7]).

Figure 2: Have we chosen the right delicacies (right) for our guests (left)?
a) A prototype travel maze problem. b) A simplified form of the problem with
piece-wise linear paths for further formal description (Sec. 2). Complexity
depends on the number of guests and the number of links in a path.

For formal analysis of the travel maze problem, we need to represent the paths
on a discrete retina of $S$-elements (Fig. 1). Then, to implement the logic of
the proof of Rosenblatt’s first theorem, each $A$-element should be an
indicator element for a possible path. For each guest-delicacy pair in Fig. 2
a) or b), an elementary perceptron must be created that returns 1 if there is
a path from this guest to this delicacy, and 0 if there are no such paths.
Thus, $n^{2}$ elementary perceptrons should be created. We can easily combine
them in a shallow network with $n^{2}$ outputs. To finalize the formal
statement we should specify the set of the possible paths. In our work, we
select a very simple specification without loops, steps back or non-
transversal intersections of paths (Fig. 2 b)).

##  2 Formal problem statement

$n$$2$$1$$n$$2$$1$ Figure 3: Game diagram with $L$ stages (a formalized and
simplified version of the travel maze problem).

Consider the following problem. There are $n$ people, each of whom owns a
single object from the set $\\{1,2,\ldots,n\\},$ and different people that own
different objects. This correspondence between people and objects can be drawn
as a diagram consisting of $n$ broken lines, each of which contains $L$ links
(Fig. 3). Each stage of the diagram consists of $n$ links and can be encoded
by a permutation or, equivalently, by permutation matrix in a natural way.
Namely, if an edge is drawn from node $i$ to node $\pi(i)$ $(i=1,2,\ldots,n),$
then the permutation can be represented in the form

$\pi=\left(\begin{matrix}1&2&\cdots&n\\\
\pi(1)&\pi(2)&\cdots&\pi(n)\end{matrix}\right)$

or by the permutation matrix $P=(p_{i,j}),$ where

$\displaystyle p_{i,j}=\begin{cases}1,&\text{if}\ j=\pi(i)\\\ 0,&\text{if}\
j\neq\pi(i).\end{cases}$

If the permutation matrix $X_{i}$ $(i=1,2,\ldots,n)$ corresponds to the $i$-th
stage then the product $X_{1}\cdot X_{2}\cdot\ldots\cdot X_{L}$ is the
permutation matrix again and it defines the correspondence ‘‘person–object’’.
It is required to construct a shallow (fully connected) neural network that
determines the correspondence ‘‘person–object’’ from the diagram.

##  3 Shallow neural network solution

$Input\ layer$$Ln^{2}\ neurons$$Inner\ layer$$(n!)^{L}\ neurons$$Output\
layer$$n^{2}\
neurons$$x_{1,1}^{(L)}$$\cdots$$x_{1,n}^{(L)}$$\vdots$$\ddots$$\vdots$$x_{n,1}^{(L)}$$\cdots$$x_{n,n}^{(L)}$$x_{1,1}^{(1)}$$\cdots$$x_{1,n}^{(1)}$$\vdots$$\ddots$$\vdots$$x_{n,1}^{(1)}$$\cdots$$x_{n,n}^{(1)}$$y_{1}$$y_{0}$$y_{(n!)^{L}-1}$$z_{1,1}$$\cdots$$z_{1,n}$$\vdots$$\ddots$$\vdots$$z_{n,1}$$\cdots$$z_{n,n}$
Figure 4: A shallow (fully connected) neural network for the travel maze
problem (Fig. 3). It differs from the classical elementary perceptron (Fig. 1)
by $n^{2}$ output neurons instead of one, and can be considered as a union of
$n^{2}$ elementary perceptrons with joint retina and hidden layer of
$A$-elements.

Arrange all the $n!$ permutations
$S_{n}=\\{\pi_{0},\pi_{1},\ldots,\pi_{n!-1}\\}.$ Then
$M=\\{P_{0},P_{1},\ldots,P_{n!-1}\\}$ is the set of the corresponding $n\times
n$ permutation matrices.

We denote the entries of the matrix $P_{k}$ by $p_{i,j}^{(k)},$ where

$p_{1,\pi_{k}(1)}^{(k)}=p_{2,\pi_{k}(2)}^{(k)}=\ldots=p_{n,\pi_{k}(n)}^{(k)}=1,$

and the other entries are equal to $0.$

Let an $L$-tuple $(X_{1},X_{2},\ldots,X_{L})$ ($X_{i}\in M$ for all
$i=1,\ldots,L$) be an $L$-tuple (a word of length $L$) over the set of
permutation matrices $M$. The number of such permutation matrices is $n!$, and
the number of $L$-tuples with elements from $M$ is $(n!)^{L}$. Consider all
such words arranged by the lexicographical order. For each word
$W_{j}=(X_{1},X_{2},\ldots,X_{L})$ with the number $j$
$(j=0,1,\ldots,(n!)^{L}-1)$ we assign the same number to the product
$X_{1}\cdot X_{2}\cdot\ldots\cdot X_{L}=P_{t_{j}}$ The matrix $P_{t_{j}}$ is
also a $n\times n$ permutation matrix.

Entries of matrices $X_{1},X_{2},\ldots,X_{L}$ are inputs of the neural
network (see Fig. 4). Each input corresponds to an input neuron ($S$-element,
Fig. 1). An inner layer $A$-neuron $y_{j}$ corresponds to the $L$-tuple
$W_{j}=(X_{1},X_{2},\ldots,X_{L})$ having the same number $j$. The neuron
$y_{j}$ should give the output signal 1, if the input vector is $W_{j}$ and
output 0 for all other $(n!)^{L}-1$ possible input vectors. Other input
vectors are impossible in our settings (Fig. 4). Each matrix element of every
permutation matrix $X_{i}$ is either 0 or 1, therefore the $L$-tuples star of
output connections of the inner neuron can be coded as a $0-1$ sequence, that
is a vertex of the $Ln^{2}$-dimensional unit cube. (Apparently, there are more
vertices than $L$-tuples of permutation matrices.) This cube is a convex body
and each vertex can be separated from all other vertices by a linear
functional. In particular, for each $j$ we can find such a linear functional
$l_{j}$ that $l_{j}(W_{j})>1/2$ and $l_{j}(W_{k})<1/2$ ($k\neq j$,
$k,j=1,\ldots,(n!)^{L}$). Here we, with some abuse of language, use the same
notation for the tuple $W_{j}$ and the correspondent vertex of the cube (a
$0-1$ sequence of the length $Ln^{2}$). Thus, each inner neuron $y_{j}$ can be
chosen in the form of the linear threshold element with the output signal
(compare to (1 and Theorem 1.1):

$y_{j}(W)=h(l_{j}(W)-1/2),$

where $h$ is the Heaviside step function. We use for the output of the neuron
$y_{j}$ the same notation $y_{j}$.

The structural difference of the shallow network (Fig. 4) for the travel maze
problem from the elementary perceptron (Fig. 1) is the number of neurons in
the output layer. For the travel maze problem the answer is the permutation
matrix with $n^{2}$ $0-1$ elements. The inner layer neuron $y_{j}$ detects the
$L$-tuple of one-step permutation matrices $W_{j}=(X_{1},X_{2},\ldots,X_{L})$.
When this input vector is detected, $y_{i}$ sends the output signal 1 to the
output neurons connected with it. For all other input vectors, it keeps
silent. The output neurons are just simple linear adders. The output neurons
$z_{qr}$ are labelled by pairs of indexes, $q,r=1,\ldots,n$. The matrix of
outputs is the permutation matrix from the start to the end of the travel. The
structure of the output connections of $y_{i}$ is determined by the input
$L$-tuple $W_{j}=(X_{1},X_{2},\ldots,X_{L})$: the connection from $y_{j}$ to
$z_{qr}$ has weight 1, if the corresponding entry $(P_{t_{j}})_{qr}=1$ and is
0 if $(P_{t_{j}})_{qr}=0$. (Recall that $P_{t_{j}}=X_{1}\cdot
X_{2}\cdot\ldots\cdot X_{L}$.)

Thus the neuron $y_{j}$ corresponds to our problem answer. Let us represent
the network functioning in more detail with explicit algebraic presentations.
All the inputs and outputs are Boolean ($0-1$) variables. We use the standard
Boolean algebra notations. In particular, $\overline{x}=1-x$

$\displaystyle y_{0}$ $\displaystyle\longrightarrow$
$\displaystyle\overbrace{P_{0}\cdot\ldots\cdot P_{0}\cdot
P_{0}}^{L}=P_{t_{0}},$ $\displaystyle y_{1}$ $\displaystyle\longrightarrow$
$\displaystyle P_{0}\cdot\ldots\cdot P_{0}\cdot P_{1}=P_{t_{1}},$
$\displaystyle\ldots$ $\displaystyle y_{n!-1}$ $\displaystyle\longrightarrow$
$\displaystyle P_{0}\cdot\ldots\cdot P_{0}\cdot P_{n!-1}=P_{t_{n!-1}},$
$\displaystyle y_{n!}$ $\displaystyle\longrightarrow$ $\displaystyle
P_{0}\cdot\ldots\cdot P_{1}\cdot P_{0}=P_{t_{n!}},$ $\displaystyle\ldots$
$\displaystyle y_{2n!-1}$ $\displaystyle\longrightarrow$ $\displaystyle
P_{0}\cdot\ldots\cdot P_{1}\cdot P_{n!-1}=P_{t_{2n!-1}},$
$\displaystyle\ldots$ $\displaystyle y_{(n!)^{L}-1}$
$\displaystyle\longrightarrow$ $\displaystyle P_{n!-1}\cdot\ldots\cdot
P_{n!-1}\cdot P_{n!-1}=P_{t_{(n!)^{L}-1}}$

Thus, if $y_{j}$ is a neuron of the inner layer, then it corresponds to the
product

$P_{t_{j}}=P_{a_{j,L-1}}\cdot P_{a_{j,L-2}}\cdot\ldots\cdot P_{a_{j,1}}\cdot
P_{a_{j,0}},$

where

$j=a_{j,L-1}(n!)^{L-1}+a_{j,L-2}(n!)^{L-2}+\ldots+a_{j,1}(n!)+a_{j,0}$

— expansion of $j$ in the base $n!.$

We need

$y_{j}(X_{1},X_{2},\ldots,X_{L})=1\ \ \Longleftrightarrow\ \
(X_{1},X_{2},\ldots,X_{L})=(P_{a_{j,L-1}},P_{a_{j,L-2}},\ldots,P_{a_{j,0}}).$

Denote

$I_{k}=\\{j:\leavevmode\nobreak\ t_{j}=k\\},\ (k=0,\ldots,n!-1),$
$M_{ij}=\\{k:\leavevmode\nobreak\ \pi_{k}(i)=j\\}=\\{k:\leavevmode\nobreak\
p_{i,j}^{(k)}=1\\}.$

Note that $|M_{ij}|=(n-1)!$.

Each neuron $y_{j}$ of the inner layer for $j\in I_{k}$ corresponds to the
same product $P_{k}$:

$y_{j}=x_{1,\pi_{a_{j,L-1}}(1)}^{(1)}\cdot
x_{2,\pi_{a_{j,L-1}}(2)}^{(1)}\ldots x_{n,\pi_{a_{j,L-1}}(n)}^{(1)}\cdot
x_{1,\pi_{a_{j,L-2}}(1)}^{(2)}\cdot x_{2,\pi_{a_{j,L-2}}(2)}^{(2)}\ldots
x_{n,\pi_{a_{j,L-2}}(n)}^{(2)}\cdot\ldots$ $\cdot
x_{1,\pi_{a_{j,0}}(1)}^{(L)}\cdot x_{2,\pi_{a_{j,0}}(2)}^{(L)}\ldots
x_{n,\pi_{a_{j,0}}(n)}^{(L)}\cdot\prod\limits_{(\alpha,\beta)\neq(i,\pi_{a_{j,s}}(i))}\overline{x_{\alpha,\beta}^{(\gamma)}}.$

The third level neurons $z_{ij}$ form the matrix $Z=(z_{ij})$ that is the
answer to this problem:

$\displaystyle z_{i,j}=\bigvee\limits_{s\in\bigcup\limits_{k\in
M_{ij}}I_{k}}y_{s},\ (i,j=1,\ldots,n).$ (2)

Since $|M_{ij}|=(n-1)!,$ $|I_{k}|=(n!)^{L-1},$ then the right-hand side in the
equality $(\ref{zij})$ contains exactly $(n-1)!\cdot(n!)^{L-1}$ terms $y_{s}.$

######  Theorem 3.1.

The constructed shallow neural network has a depth of $3$,

$(L+1)n^{2}+(n!)^{L}$

neurons, and

$(L+1)n^{2}(n!)^{L}$

connections between neurons.

The constructed network memorizes products in all $L$-tuples of permutation
matrices, recognizes the input $L$-tuple of permutations, and sends the
product to the output.

######  Example 1.

Consider $n=2,L=3.$ Then

$\pi_{0}=\begin{pmatrix}1&2\\\ 1&2\end{pmatrix},\pi_{1}=\begin{pmatrix}1&2\\\
2&1\end{pmatrix},P_{0}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix},P_{1}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}.$

$y_{0}$$P_{0}P_{0}P_{0}=P_{0}$$y_{4}$$P_{0}P_{0}P_{1}=P_{1}$$y_{2}$$P_{0}P_{1}P_{0}=P_{1}$$y_{3}$$P_{0}P_{1}P_{1}=P_{0}$$y_{1}$$P_{1}P_{0}P_{0}=P_{1}$$y_{5}$$P_{1}P_{0}P_{1}=P_{0}$$y_{6}$$P_{1}P_{1}P_{0}=P_{0}$$y_{7}$$P_{1}P_{1}P_{1}=P_{1}$
Figure 5: The case $n=2,L=3$.

$X_{1}=\begin{pmatrix}x_{11}^{(1)}&x_{12}^{(1)}\\\
x_{21}^{(1)}&x_{22}^{(1)}\end{pmatrix},X_{2}=\begin{pmatrix}x_{11}^{(2)}&x_{12}^{(2)}\\\
x_{21}^{(2)}&x_{22}^{(2)}\end{pmatrix},X_{3}=\begin{pmatrix}x_{11}^{(3)}&x_{12}^{(3)}\\\
x_{21}^{(3)}&x_{22}^{(3)}\end{pmatrix}.$

For example, we have $5=1\cdot(2!)^{2}+0\cdot(2!)+1$ for $j=5$ therefore

$y_{5}=x_{1,\pi_{1}(1)}^{(1)}\cdot x_{2,\pi_{1}(2)}^{(1)}\cdot
x_{1,\pi_{0}(1)}^{(2)}\cdot x_{2,\pi_{0}(2)}^{(2)}\cdot
x_{1,\pi_{1}(1)}^{(3)}\cdot
x_{2,\pi_{1}(2)}^{(3)}\cdot\prod\limits_{(\alpha,\beta)\neq(i,\pi_{a_{j,s}}(i))}\overline{x_{\alpha,\beta}^{(\gamma)}}=$
$=x_{1,2}^{(1)}\cdot x_{2,1}^{(1)}\cdot x_{1,1}^{(2)}\cdot x_{2,2}^{(2)}\cdot
x_{1,2}^{(3)}\cdot
x_{2,1}^{(3)}\cdot\overline{x_{1,1}^{(1)}}\cdot\overline{x_{2,2}^{(1)}}\cdot\overline{x_{1,2}^{(2)}}\cdot\overline{x_{2,1}^{(2)}}\cdot\overline{x_{1,1}^{(3)}}\cdot\overline{x_{2,2}^{(3)}}.$

We can write similar expressions for all other $y_{j}.$

In this case, we have $I_{0}=\\{0,3,5,6\\},$ $I_{1}=\\{1,2,4,7\\}$ and
$M_{11}=\\{0\\},M_{12}=\\{1\\},M_{21}=\\{1\\},M_{22}=\\{0\\},$ so

$z_{1,1}=z_{2,2}=y_{0}\vee y_{3}\vee y_{5}\vee y_{6},$
$z_{1,2}=z_{2,1}=y_{1}\vee y_{2}\vee y_{4}\vee y_{7}.$

######  Example 2.

Let $n=3,L=2.$ Then

$\pi_{0}=\begin{pmatrix}1&2&3\\\
1&2&3\end{pmatrix},\pi_{1}=\begin{pmatrix}1&2&3\\\
1&3&2\end{pmatrix},\pi_{2}=\begin{pmatrix}1&2&3\\\ 2&1&3\end{pmatrix},$
$\pi_{3}=\begin{pmatrix}1&2&3\\\
2&3&1\end{pmatrix},\pi_{4}=\begin{pmatrix}1&2&3\\\
3&1&2\end{pmatrix},\pi_{5}=\begin{pmatrix}1&2&3\\\ 3&2&1\end{pmatrix}$
$P_{0}=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\\\
\end{pmatrix},P_{1}=\begin{pmatrix}1&0&0\\\ 0&0&1\\\ 0&1&0\\\
\end{pmatrix},P_{2}=\begin{pmatrix}0&1&0\\\ 1&0&0\\\ 0&0&1\\\ \end{pmatrix},$
$P_{3}=\begin{pmatrix}0&1&0\\\ 0&0&1\\\ 1&0&0\\\
\end{pmatrix},P_{4}=\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\\\
\end{pmatrix},P_{5}=\begin{pmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\\\ \end{pmatrix}.$

$\cdot$ | $P_{0}$ | $P_{1}$ | $P_{2}$ | $P_{3}$ | $P_{4}$ | $P_{5}$
---|---|---|---|---|---|---
$P_{0}$ | $P_{0}$ | $P_{1}$ | $P_{2}$ | $P_{3}$ | $P_{4}$ | $P_{5}$
$P_{1}$ | $P_{1}$ | $P_{0}$ | $P_{3}$ | $P_{2}$ | $P_{5}$ | $P_{4}$
$P_{2}$ | $P_{2}$ | $P_{4}$ | $P_{0}$ | $P_{5}$ | $P_{1}$ | $P_{3}$
$P_{3}$ | $P_{3}$ | $P_{5}$ | $P_{1}$ | $P_{4}$ | $P_{0}$ | $P_{2}$
$P_{4}$ | $P_{4}$ | $P_{2}$ | $P_{5}$ | $P_{0}$ | $P_{3}$ | $P_{1}$
$P_{5}$ | $P_{5}$ | $P_{3}$ | $P_{4}$ | $P_{1}$ | $P_{2}$ | $P_{0}$

$P_{0}P_{0}=P_{0}$$y_{0}$$\cdots$$\cdots$$P_{2}P_{3}=P_{5}$$\cdots$$y_{15}$$\cdots$$P_{3}P_{2}=P_{1}$$\cdots$$y_{20}$$\cdots$$P_{5}P_{5}=P_{0}$$y_{35}$
Figure 6: The case $n=3,L=2$.

$X_{1}=\begin{pmatrix}x_{11}^{(1)}&x_{12}^{(1)}&x_{13}^{(1)}\\\
x_{21}^{(1)}&x_{22}^{(1)}&x_{23}^{(1)}\\\
x_{31}^{(1)}&x_{32}^{(1)}&x_{33}^{(1)}\end{pmatrix},X_{2}=\begin{pmatrix}x_{11}^{(2)}&x_{12}^{(2)}&x_{13}^{(2)}\\\
x_{21}^{(2)}&x_{22}^{(2)}&x_{23}^{(2)}\\\
x_{31}^{(2)}&x_{32}^{(2)}&x_{33}^{(2)}\end{pmatrix}.$

For example, we have $15=2\cdot(3!)+3$ for $j=15$ so

$y_{15}=x_{1,\pi_{2}(1)}^{(1)}\cdot x_{2,\pi_{2}(2)}^{(1)}\cdot
x_{2,\pi_{2}(3)}^{(1)}\cdot x_{1,\pi_{3}(1)}^{(2)}\cdot
x_{2,\pi_{3}(2)}^{(2)}\cdot
x_{2,\pi_{3}(3)}^{(2)}\cdot\prod\limits_{(\alpha,\beta)\neq(i,\pi_{a_{j,s}}(i))}\overline{x_{\alpha,\beta}^{(\gamma)}}=$
$=x_{1,2}^{(1)}\cdot x_{2,1}^{(1)}\cdot x_{3,3}^{(1)}\cdot x_{1,2}^{(2)}\cdot
x_{2,3}^{(2)}\cdot
x_{3,1}^{(2)}\cdot\overline{x_{1,1}^{(1)}}\cdot\overline{x_{1,3}^{(1)}}\cdot\overline{x_{2,2}^{(1)}}\cdot\overline{x_{2,3}^{(1)}}\cdot\overline{x_{3,1}^{(1)}}\cdot\overline{x_{3,2}^{(1)}}\cdot\overline{x_{1,1}^{(2)}}\cdot\overline{x_{1,3}^{(2)}}\cdot\overline{x_{2,1}^{(2)}}\cdot\overline{x_{2,2}^{(2)}}\cdot\overline{x_{3,2}^{(2)}}\cdot\overline{x_{3,3}^{(2)}}.$

We can write similar expressions for the others $y_{j}.$

In this case, we have

$M_{11}=\\{0,1\\},M_{12}=\\{2,3\\},M_{13}=\\{4,5\\},$
$M_{21}=\\{2,4\\},M_{22}=\\{0,5\\},M_{23}=\\{1,3\\},$
$M_{31}=\\{3,5\\},M_{32}=\\{1,4\\},M_{33}=\\{0,2\\}$

and

$I_{0}=\\{0,7,14,22,27,35\\},I_{1}=\\{1,6,16,20,29,33\\},I_{2}=\\{2,9,12,23,25,34\\},$
$I_{3}=\\{3,8,17,18,28,31\\},I_{4}=\\{4,11,13,21,24,32\\},I_{5}=\\{5,10,15,19,26,30\\}.$

Thus

$z_{1,1}=\bigvee_{s\in I_{0}\cup I_{1}}y_{s}=y_{0}\vee y_{7}\vee y_{14}\vee
y_{22}\vee y_{27}\vee y_{35}\vee y_{1}\vee y_{6}\vee y_{16}\vee y_{20}\vee
y_{29}\vee y_{33},$ $z_{1,2}=\bigvee_{s\in I_{2}\cup I_{3}}y_{s}=y_{2}\vee
y_{9}\vee y_{12}\vee y_{23}\vee y_{25}\vee y_{34}\vee y_{3}\vee y_{8}\vee
y_{17}\vee y_{18}\vee y_{28}\vee y_{31},$ $z_{1,3}=\bigvee_{s\in I_{4}\cup
I_{5}}y_{s}=y_{4}\vee y_{11}\vee y_{13}\vee y_{21}\vee y_{24}\vee y_{32}\vee
y_{5}\vee y_{10}\vee y_{15}\vee y_{19}\vee y_{26}\vee y_{30},$
$z_{2,1}=\bigvee_{s\in I_{2}\cup I_{4}}y_{s}=y_{2}\vee y_{9}\vee y_{12}\vee
y_{23}\vee y_{25}\vee y_{34}\vee y_{4}\vee y_{11}\vee y_{13}\vee y_{21}\vee
y_{24}\vee y_{32},$ $z_{2,2}=\bigvee_{s\in I_{0}\cup I_{5}}y_{s}=y_{0}\vee
y_{7}\vee y_{14}\vee y_{22}\vee y_{27}\vee y_{35}\vee y_{5}\vee y_{10}\vee
y_{15}\vee y_{19}\vee y_{26}\vee y_{30},$ $z_{2,3}=\bigvee_{s\in I_{1}\cup
I_{3}}y_{s}=y_{1}\vee y_{6}\vee y_{16}\vee y_{20}\vee y_{29}\vee y_{33}\vee
y_{3}\vee y_{8}\vee y_{17}\vee y_{18}\vee y_{28}\vee y_{31},$
$z_{3,1}=\bigvee_{s\in I_{3}\cup I_{5}}y_{s}=y_{3}\vee y_{8}\vee y_{17}\vee
y_{18}\vee y_{28}\vee y_{31}\vee y_{5}\vee y_{10}\vee y_{15}\vee y_{19}\vee
y_{26}\vee y_{30},$ $z_{3,2}=\bigvee_{s\in I_{1}\cup I_{4}}y_{s}=y_{1}\vee
y_{6}\vee y_{16}\vee y_{20}\vee y_{29}\vee y_{33}\vee y_{4}\vee y_{11}\vee
y_{13}\vee y_{21}\vee y_{24}\vee y_{32},$ $z_{3,3}=\bigvee_{s\in I_{0}\cup
I_{2}}y_{s}=y_{0}\vee y_{7}\vee y_{14}\vee y_{22}\vee y_{27}\vee y_{35}\vee
y_{2}\vee y_{9}\vee y_{12}\vee y_{23}\vee y_{25}\vee y_{34}.$

##  4 Deep neural network solution

The calculation of the matrix $Z=X_{1}\cdot X_{2}\cdot\ldots\cdot X_{L}$ can
be performed using a deep learning network, multiplying sequentially:
$Y_{1}=X_{1},$ $Y_{k}=Y_{k-1}\cdot X_{k},$ $(k=2,\ldots,L).$ Then $Z=Y_{L}.$
The network diagram is shown in the Fig. 7.

Let $X_{k}=(x_{ij}^{(k)}),$ $Y_{k}=(y_{ij}^{(k)}).$ Then

$y_{ij}^{(k)}=y_{i1}^{(k-1)}\cdot x_{1j}^{(k)}\oplus y_{i2}^{(k-1)}\cdot
x_{2j}^{(k)}\oplus\ldots\oplus y_{in}^{(k-1)}\cdot x_{nj}^{(k)}.$

To calculate the entries of matrices, we use conjunction and addition modulo
$2.$

$X_{1}$$X_{2}$$X_{3}$$X_{L}$$Y_{2}$$Y_{3}$$Z=Y_{L}$$Y_{L-1}$ Figure 7: A deep
neural network diagram for simplified travel maze problem.

######  Theorem 4.1.

The constructed deep neural network has a depth of $L$,

$(2L-1)n^{2}$

neurons, and

$2(L-1)n^{3}$

connections between neurons.

##  5 Neural network for $r$-bounded problem

A problem is called $r$-bounded ($0\leq r\leq n-1$) if the inequality
$|\pi_{j_{k}}(i)-i|\leq r$ holds for all $i=1,\ldots,n;$ $k=1,\ldots,L.$ It
means that the corresponding permutation matrices are banded matrices with the
bandwidth $r+1,$ i.e. $x_{ij}=0$ for $|i-j|\geq r+1.$

Let $A$ be a banded matrix of the bandwidth $r+1.$ The maximum number of
nonzero entries in an arbitrary row of $A$ at most $2r+1.$ The number of
nonzero entries in $A$ at most

$N_{r}=n^{2}-(n-r)(n-r-1)=n(2r+1)-(r^{2}+r).$

If $A$ and $B$ are banded matrices of the bandwidth $r+1$ and $t+1$,
respectively, then the product $AB$ is a banded matrix of bandwidth $r+t+1.$

######  Theorem 5.1.

For a $r$-bounded problem, there is a shallow neural network with a depth of
$3$,

$L\cdot N_{r}+n^{2}+(n!)^{L}$

neurons, and

$(L\cdot N_{r}+n^{2})\cdot(n!)^{L}$

connections between them.

######  Theorem 5.2.

For a $r$-bounded problem, there is a deep neural network with a depth $L,$

$L\cdot N_{r}+\sum\limits_{i=2}^{L}N_{ir}\ \text{neurons if}\ Lr\leq n-1,$
$L\cdot
N_{r}+\sum\limits_{i=2}^{[\frac{n-1}{r}]}N_{ir}+n^{2}\cdot\left(L-\left[\frac{n-1}{r}\right]\right)\
\text{neurons if}\ Lr>n-1,$

,

$2\sum\limits_{i=2}^{L}(ir+1)N_{ir}\ \text{connections between neurons if}\
Lr\leq n-1,$ $\text{and
}2\sum\limits_{i=2}^{[\frac{n-1}{r}]}(ir+1)N_{ir}+n^{2}\cdot(2r+n+1)\cdot\left(L-\left[\frac{n-1}{r}\right]\right)\
\text{connections if}\ Lr>n-1.$

##  6 Conclusion and outlook

  * 1.

Shallow neural network combined from elementary Rosenblatt’s perceptrons can
solve the travel maze problem, in accordance with Rosenblatt’s first theorem.

  * 2.

Complexity of the constructed solution of the travel maze problem by deep
network is much smaller than for the solution provided by the shallow network
(the main terms are $2Ln^{2}$ versus $(n!)^{L}$ for the numbers of neurons and
$2L^{3}$ versus $Ln^{2}(n!)^{L}$ for the numbers of connections).

The first result is important in the context of the widespread myth that
elementary Rosenblatt’s perceptrons have limited abilities and that Minsky and
Papert revealed these limitations. This mythology has penetrated even into the
encyclopedic literature [8].

Original Rosenblatt’s perceptrons [1] (Fig. 1) can solve any problem about
classification of binary images and, after minor modification, even wider.
This simple fact was proven in Rosenblatt’s first theorem, and nobody
criticised this theorem and proof. The universal representation property of
shallow neural networks were studied in 1990s from different point of view,
including approximation of real-valued functions [9] and evaluation of upper
bounds on rates of approximation [10]. Elegant analysis of shallow neural
networks involved infinite-dimensional hidden layers [11] and upper bounds
were derived on the speed of decrease of approximation error as the number of
network units increases. Abilities and limitations of shallow networks were
reviewed recently in detail [12].

Of course, a single $R$-element can solve only linearly separable problems,
and, obviously, not all problems are linearly separable. Stating this trivial
statement does not require any intellectual effort. Minsky and Papert [5]
considered much more complex systems then a single linear threshold
$R$-element. They studied the same elementary perceptrons that Rosenblatt did
(Fig. 1) with one restriction: receptive fields of $A$-elements are bounded.
These limitation may assume a sufficiently small diameter of the receptive
field (the most common condition), or limited number of input connections of
each $A$-neuron. Elementary perceptrons with such restriction have limited
abilities: if we have only local information, then we cannot solve such a
global problem as checking the connectivity of a set or the travel maze
problem with one glance. We should integrate the local knowledge into global
criterion using a sequence of steps. This intuitively clear statement was
accurately formalised and proved for the parity problem by Minsky and Papert
[5].

Without restrictions, elementary perceptrons are omnipotent. In particular,
they can solve the travel maze problem in the proposed form, but the
complexity of solutions can be huge (Theorem 3.1). On the contrary, the deep
network solution (Theorem 4.1) is much simpler and seems to be much more
natural. It combined solution from the one-step permutations locally, step by
step, whereas the shallow network operated by all possible global paths.
Restriction of the possible paths of travel by bounded radius of a single step
(Sec. 5) does not change the situation qualitatively. (The restricted problem
is simpler than the original one. This should not be confused with the
possible network limitations, that complicate all problems.)

The second observation seems to be more important than the first one: the
properly selected deep solutions can be much simpler than the shallow
solutions. In the contrast to the widely discussed huge deep structures and
their surprising efficiency (see the detailed exposition of mathematics of
deep learning in [13]) the relatively small but deep neural networks are non-
surprisingly effective for solution of problems where local information should
be integrated into global decision, like in the discussed version of the
travel maze problem. These networks combine the benefits of the fine-grained
parallel procession and the solutions of problems at a glance with the
possibility to emulate logic of sequential data analysis, when it is
necessary. The important question in this context is: ‘‘How deep should be the
depth?’’ [14]. The answer depends on the problem.

The open question remains: are the complexity estimates sharp? How far are our
solutions from the best ones? We do not expect that this problem has a simple
solution because even for multiplication of $n\times n$ matrices no final
solution has yet been found despite great efforts and significant progress
(for the best of our knowledge, the latest improvement from $n^{2.37287}$ to
$n^{2.37286}$ was achieved recently [15]). Another open question might attract
attention: Analyse the original geometric travel maze problem (see Fig. 2
instead of its more algebraic simplification presented in Fig. 3). It includes
many non-trivial tasks, for example, convenient discrete representation of the
possible paths with bounded curvature, lengths and ends, and constructive
selection of $\epsilon$-networks in the space of such paths for preparing the
input weights of of $A$-elements.

Complexity of functions computable by deep and shallow networks used for
solution of classification problem were compared for the same complexity of
networks [16]. Complexity of functions was measured using topological
invariants of the superlevel sets. The results seem to support the idea that
deep networks can address more difficult problems with the same number of
resources.

The problem of effective parallelism pretends to be the central problem which
is being solved by the whole neuroinformatics [17]. It has long been known
that the efficiency of parallel computations increases slower than the number
of processors. There is a well known ‘‘Minsky hypothesis’’: efficiency of a
parallel system increases (approximately) proportionally to logarithm of the
number of processors; at least, it is a concave function. Shallow neural
networks pretend to solve all problems in one step, but the cost for that may
be enormous number of resources. Deep networks make possible a trade-off
between resources (number of elements) and the time needed to solve a problem,
since they can combine the efficient parallelism of neural networks with
elements of sequential reasoning. Therefore, neural networks can be a useful
tool for solving the problem of efficient fine-grained parallel computing if
we can answer the question: how deep should the depths be for different
classes of problems. The case study presented in our note gives an example of
significant increase of efficiency for a reasonable choice of depth.

## Acknowledgments

The project is supported by the Ministry of Science and Higher Education of
the Russian Federation (Project No 075-15-2020-808).

## References

  * [1] Rosenblatt, F., (1962). Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan Books.
  * [2] Venkatesh, B., Anuradha, J. (2019). A review of feature selection and its methods. Cybernetics and Information Technologies, 19(1), 3–26. https://doi.org/10.2478/cait-2019-0001
  * [3] Al-Tashi, Q., Abdulkadir, S. J., Rais, H. M., Mirjalili, S., Alhussian, H. (2020). Approaches to multi-objective feature selection: A systematic literature review. IEEE Access, 8, 125076–125096. https://doi.org/10.1109/ACCESS.2020.3007291
  * [4] Rong, M., Gong, D., Gao, X. (2019). Feature selection and its use in big data: challenges, methods, and trends. IEEE Access, 7, 19709–19725. https://doi.org/10.1109/ACCESS.2019.2894366
  * [5] Minsky, M., Papert, S. (1988). Perceptrons, MIT Press, Cambridge, MA. expanded ed.
  * [6] Seifert B.G. (1992). Binary classifiers, pcrceptrons and connectedness in metric spaces and graphs. Journal of Pure and Applied Algebra 83, 197–203. https://doi.org/10.1016/0022-4049(92)90162-9
  * [7] Albergante L, Mirkes E, Bac J, Chen H, Martin A, Faure L, Barillot E, Pinello L, Gorban A, Zinovyev A. Robust and Scalable Learning of Complex Intrinsic Dataset Geometry via ElPiGraph. Entropy. 2020; 22(3):296. https://doi.org/10.3390/e22030296
  * [8] Bishop, J. M. (2015). History and Philosophy of Neural Networks. In: Hisao Ishibuchi, ed. Encyclopedia of Life Support Systems (EOLSS): Computational Intelligence. UNESCO.
  * [9] Ito, Y. (1992). Finite mapping by neural networks and truth functions. Mathematical Scientist, 17, 69-77.
  * [10] Kůrková, V., Savický, P., Hlavávcková, K. (1998). Representations and rates of approximation of real-valued Boolean functions by neural networks. Neural Networks, 11(4), 651-659. https://doi.org/10.1016/s0893-6080(98)00039-2
  * [11] Kainen, P. C., Kůrková, V. (2009). An integral upper bound for neural network approximation. Neural Computation, 21(10), 2970-2989. https://doi.org/10.1162/neco.2009.04-08-745
  * [12] Kůrková, V. (2020). Limitations of Shallow Networks. In: Oneto, L., Navarin, N., Sperduti, A., Anguita, D. (eds) Recent Trends in Learning From Data. Studies in Computational Intelligence, vol 896. Springer, Cham. pp. 129-154. https://doi.org/10.1007/978-3-030-43883-8_6
  * [13] Berner, J., Grohs, P. Kutyniok, G., Petersen P. (2021). The Modern Mathematics of Deep Learning, arXiv:2105.04026 [cs.LG]. https://doi.org/10.48550/arXiv.2105.04026
  * [14] Gorban, A. N., Mirkes, E. M., Tyukin, I. Y. (2020). How deep should be the depth of convolutional neural networks: a backyard dog case study. Cognitive Computation, 12(2), 388–397. https://doi.org/10.1007/s12559-019-09667-7
  * [15] Alman, J., Vassilevska Williams, V. (2021). A Refined Laser Method and Faster Matrix Multiplication, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) 522–539, https://doi.org/10.1137/1.9781611976465.32
  * [16] Bianchini, M., Scarselli, F. (2014). On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE transactions on neural networks and learning systems, 25(8), 1553-1565. https://doi.org/10.1109/TNNLS.2013.2293637
  * [17] Gorban, A. N. (1999). Neuroinformatics: What are us, where are we going, how to measure our way? A lecture given at the USA-NIS Neurocomputing opportunities workshop, Washington DC, July 1999 (Associated with IJCNN’99), arXiv:cond-mat/0307346 [cond-mat.dis-nn], https://doi.org/10.48550/arXiv.cond-mat/0307346