Understanding Deep Neural Networks via Linear Separability of Hidden
  Layers
In this paper, we measure the linear separability of hidden layer outputs to
study the characteristics of deep neural networks. In particular, we first
propose Minkowski difference based linear separability measures (MD-LSMs) to
evaluate the linear separability degree of two points sets. Then, we
demonstrate that there is a synchronicity between the linear separability
degree of hidden layer outputs and the network training performance, i.e., if
the updated weights can enhance the linear separability degree of hidden layer
outputs, the updated network will achieve a better training performance, and
vice versa. Moreover, we study the effect of activation function and network
size (including width and depth) on the linear separability of hidden layers.
Finally, we conduct the numerical experiments to validate our findings on some
popular deep networks including multilayer perceptron (MLP), convolutional
neural network (CNN), deep belief network (DBN), ResNet, VGGNet, AlexNet,
vision transformer (ViT) and GoogLeNet.
Chao Zhang, Xinyu Chen, Wensheng Li, Lixue Liu, Wei Wu, Dacheng Tao
# Understanding Deep Neural Networks via Linear Separability of Hidden Layers

###### Abstract

In this paper, we measure the linear separability of hidden layer outputs to study the characteristics of deep neural networks. In particular, we first propose Minkowski difference based linear separability measures (MD-LSMs) to evaluate the linear separability degree of two points sets. Then, we demonstrate that there is a synchronicity between the linear separability degree of hidden layer outputs and the network training performance, _i.e._, if the updated weights can enhance the linear separability degree of hidden layer outputs, the updated network will achieve a better training performance, and vice versa. Moreover, we study the effect of activation function and network size (including width and depth) on the linear separability of hidden layers. Finally, we conduct the numerical experiments to validate our findings on some popular deep networks including multilayer perceptron (MLP), convolutional neural network (CNN), deep belief network (DBN), ResNet, VGGNet, AlexNet, vision transformer (ViT) and GoogLeNet.

## 1 Introduction

Deep neural networks have been successfully used to solve many complicated learning tasks, for example, computer vision [1, 2, 3], natural language processing [4, 5, 6] and other engineering applications [7, 8]. The empirical observation that the large network size is beneficial to the generalization performance of deep networks, is contrary to the traditional view of statistical learning theory, which deems that high model complexity will cause the overfitting. In recent years, many research works attempt to explain why deep neural networks perform well in these difficult tasks by using some theoretical analysis tools such as statistical learning theory (SLT) [9], PAC-Bayes framework [10] and neural tangent kernel (NTK) [11]. However, there still remains a gap between these theoretical results and the user experiences of deep neural networks. For example, following the classical STL methods, the complexity measures of deep networks were expressed as increasing functions w.r.t. the network size, and the relevant generalization bounds will become loose when the network size is large (_cf._[12, 13, 14, 15]). Moreover, some results on NTK and over-parameterized neural networks are obtained under the assumption that the network width is infinite (_cf._[16, 17, 18, 19, 20, 21, 22]). Some recent theoretical works on deep neural networks are summarized in the appendix (part A).

### Background and Motivation

Two point sets are said to be linearly separable if they can be correctly split by using a hyperplane, and the concept of linear separability plays an important part in measuring the capability of neural
networks [23, 24, 25]. In the literature, there are two main research issues on the linear separability of neural networks: 1) whether the current network can achieve all dichotomies, _i.e.,_ the mapping capability [26]; and 2) how many dichotomies can be recorded by a network with the specific structure, _i.e.,_ the memory capability [27, 28]. However, to the best of our knowledge, there is rarely few work to consider the layer-wise changes of the linear separability degree of two point sets when they pass through a network with multiple hidden layers.

Our study is initially motivated by the relationship between the linear separability degree of hidden layer outputs and the process of training networks. We would like to know whether the linear separability degree of hidden layer outputs increases when the training accuracy increases. If applicable, the linear separability degree can be treated as a criterion for evaluating the performance of each hidden layer during the training phase.

Consider a one-hidden-layer MLP net\((\cdot):\mathbb{R}^{N}\rightarrow\{0,1\}\) with the output-layer weight vector \(\mathbf{w}\) and the hidden-layer weight matrix \(\mathbf{V}\). Let \(\mathrm{hid}(\cdot):\mathbb{R}^{N}\rightarrow\mathbb{R}^{H}\) be the hidden layer of the MLP, and \(\mathrm{hid}(\mathcal{X})\) be the set of hidden layer outputs w.r.t. the input set \(\mathcal{X}:=\{\mathbf{x}_{m}\}_{m=1}^{M}\). The set \(\mathrm{hid}(\mathcal{X})\) is called hidden-layer outputs in the following discussion, if no confusion arises. Denote \(\triangle\mathbf{w}\) and \(\triangle\mathbf{V}\) as the weight updates provided by a training algorithm implemented on the training set \(\mathcal{S}=\{(\mathbf{x}_{m},\mathbf{y}_{m})\}_{m=1}^{M}\subset\mathbb{R}^{ N}\times\{0,1\}\). The updated network is denoted as net\({}^{\prime}(\cdot)\) with updated weights \(\mathbf{w}^{\prime}=\mathbf{w}+\triangle\mathbf{w}\) and \(\mathbf{V}^{\prime}=\mathbf{V}+\triangle\mathbf{V}\). Denote \(\mathrm{hid}^{\prime}(\cdot)\) as the updated hidden layer with the weights \(\mathbf{V}^{\prime}\). Under these notations, we obtain the following theorem which motivates the research of this paper:

**Theorem 1** (Synchronicity).: _Assume that the updated weights \(\mathbf{w}^{\prime}\) achieves the highest classification accuracy on \(\mathcal{S}\) when the hidden-layer weights of net\({}^{\prime}(\cdot)\) is updated to be \(\mathbf{V}^{\prime}\). Then, net\({}^{\prime}(\cdot)\) has higher classification accuracy on \(\mathcal{S}\) than net\((\cdot)\) if and only if the linear separability degree of \(\mathrm{hid}^{\prime}(\mathcal{X})\) is larger than that of \(\mathrm{hid}(\mathcal{X})\)._

This theorem demonstrates the synchronicity between the linear separability degree of hidden layer outputs and the network training performance. When training a network, the change of the linear separability degree of hidden layer outputs synchronizes with the change of the training accuracy. Different from the existing works on the theoretical analysis of neural networks, the linear separability degree provides a feasible manner to directly study the relationship between the structure parameters and the network capability. Accordingly, a desired linear separability measure (LSM) should meet the following requirements:

1. It should have a low computational cost, because we would like to layer-wisely examine the linear separability degree of the hidden-layer outputs after each training iteration;
2. It should be insensitive to the outliers, because the stochastic gradient descent methods sometimes cause abnormal hidden layer outputs;
3. It should be of a well-defined mathematical form in order to facilitate the further theoretical analysis.

Some mathematical terms mentioned in the existing works actually can be treated as LSMs of two point sets, for example, the generalized Rayleigh quotient \(J_{\omega}=\max_{\boldsymbol{\omega}}\frac{\boldsymbol{\omega}^{T}\mathbf{S}_ {\boldsymbol{\omega}}\boldsymbol{\omega}}{\boldsymbol{\omega}^{T}\mathbf{S}_ {\boldsymbol{\omega}}\boldsymbol{\omega}}\) in Fisher linear discriminant analysis (LDA) and the sum of slack variables in linear support vector machine (L-SVM) with soft margin.1 However, the LDA-based LSM, which is based on the means of point sets, is sensitive to the outliers in the sets and has a high computational cost because of eigenvalue
decomposition; and the computation of the L-SVM based LSM is still time-consuming especially when the sample size is large. Moreover, Ben-Israel _et al_. [29] introduce the linear divisible angle to measure the linear separability degree of two point sets, where the labels of the data are treated as a new attribute to convert the dimension of points from \(N\) to \(N+1\), and then Fisher LDA is used to compute the generalized Rayleigh quotient of the converted points. Gabidullina _et al_. [30] adopted the smallest thickness of the classified hyperplane as the LSM for the linearly inseparable sets. Since this measure is computed via a minimax optimization problem, it has a high computational cost as well.

### Overview of Main Results

In Section 2, we propose the Minkowski difference-based LSM (MD-LSM) for two point sets, and provide an algorithm of finding the largest linearly separable subsets of arbitrary two linearly inseparable sets. Then, we show the relationship between the linear separability degree of two linearly inseparable sets and the best classification accuracy provided by all possible linear models. Moreover, we provide the alternative versions of MD-LSM to reduce the cost of computing the MD-LSM of each hidden layer after each training epoch.

In Section 3, we study the effects of activation function and network size on the linear separability of hidden layers. First, the hidden layer of a neural networks is regarded as the pseudo-linear mapping (PLM) (_cf_. [27]). Then, we provide a sufficient condition that a PLM changes the relative position between one Minkowski difference (MD) point and the splitting hyperplane. Moreover, based on the random matrix theory, we have proven that the increase of network size can enlarge the probability of increasing the linear separability degree of hidden layer outputs.

In Section 4, we conduct the numerical experiments to validate the theoretical findings of this paper on some well-known networks including multilayer perceptron (MLP) [31], convolutional neural network (CNN) [32], deep brief network (DBN) [33], ResNet [34], VGGNet [35], AlexNet [36], vision transformer (ViT) [37] and GoogLeNet [38] in classification tasks, respectively.

In Section 5, we discuss the difference between the proposed MD-LSM and Fisher LDA, and then explain why we use MD-LSMs to evaluate the linear separability degree of hidden layer outputs rather than the Rayleigh quotient in Fisher LDA. In Section 6, we prove the main results of this paper, and the last section concludes the paper. In the appendix, we briefly sketch the recent works on theoretical analysis of deep networks (part A), and then provide the complete experimental report (part B).

## 2 Minkowski Difference Based Linear Separability Measure (MD-LSM)

In this section, we present the concept of MD-LSM for two point sets and then give an algorithm to find the maximum linearly separable subset of two linearly inseparable point sets. Moreover, we provide some alternative versions of MD-LSMs with low computation cost.

### Minkowski Difference and Maximum Linearly Separable Subset

First, we introduce the concept of Minkowski difference (MD), which has been widely used for the applications in many areas such as data classification [39, 40], motion planning for robots [41], real-time collision detection [42] and computer graphics [43, 44].
**Definition 2** (Minkowski Difference).: _Let \(\mathcal{A}=\{\mathbf{a}_{1},\cdots,\mathbf{a}_{I}\}\subset\mathbb{R}^{N}\) and \(\mathcal{B}=\{\mathbf{b}_{1},\cdots,\mathbf{b}_{J}\}\subset\mathbb{R}^{N}\) be two point sets. Then, the Minkowski difference between the two sets is defined as_

\[\mathrm{MD}(\mathcal{A},\mathcal{B}):=\big{\{}\mathbf{m}_{ij}:=\mathbf{a}_{i}- \mathbf{b}_{j}\in\mathbb{R}^{N}\mid\mathbf{a}_{i}\in\mathcal{A},\;\mathbf{b}_{ j}\in\mathcal{B}\big{\}}.\]

Based on Minkowski difference, we convert the linear separability of two point sets into the relative position relationship between a point set and a hyperplane that passes the origin.

**Theorem 3**.: _Two points sets \(\mathcal{A},\mathcal{B}\in\mathbb{R}^{N}\) are linearly separable if and only if there exists a vector \(\boldsymbol{\omega}\in\mathbb{R}^{N}\) such that all points of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) locates in one side of the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{x}=0\), \(\mathbf{x}\in\mathbb{R}^{N}\)._

We note that the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\) parallels to the separating hyperplane between the two classes \(\mathcal{A}\) and \(\mathcal{B}\) if they are linearly separable. Additionally, if the two sets \(\mathcal{A}\) and \(\mathcal{B}\) are linearly inseparable, some points of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) will lie in one side of the hyperplane and the rest lie in the other side:

**Definition 4** (Minor and Major Sides).: _Given a hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\), if more than half points of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) lie in one side of \(\boldsymbol{\omega}^{T}\mathbf{m}=0\), then this side is said to be the major side of the hyperplane; and accordingly, the other side of \(\boldsymbol{\omega}^{T}\mathbf{m}=0\) is said to be the minor side of the hyperplane._

Furthermore, denote \(\mathrm{major}_{\boldsymbol{\omega}}(\mathrm{MD}(\mathcal{A},\mathcal{B}))\) (resp. \(\mathrm{minor}_{\boldsymbol{\omega}}(\mathrm{MD}(\mathcal{A},\mathcal{B}))\)) as the subset of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) containing all points of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) that locate in the major (resp. minor) side of \(\boldsymbol{\omega}^{T}\mathbf{m}=0\). If some points \(\mathbf{m}_{ij}\) located at the minor side of the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\), we can remove the corresponding original points \(\mathbf{a}_{i}\) (resp. \(\mathbf{b}_{j}\)) from \(\mathcal{A}\) (resp. \(\mathcal{B}\)) to form two new sets \(\mathcal{A}_{1}\) and \(\mathcal{B}_{1}\), which are linearly separable.

**Definition 5**.: _The set \(\mathrm{MaxLS}(\mathcal{A},\mathcal{B})\) is said to be the maximum linearly-separable subset of \(\mathcal{A}\cup\mathcal{B}\) if_

\[\mathrm{MaxLS}(\mathcal{A},\mathcal{B}):=\mathcal{A}_{\circ}\cup\mathcal{B}_{ \circ}=\operatorname*{arg\,max}_{\mathcal{A}^{\prime}\subset\mathcal{A}, \mathcal{B}^{\prime}\subset\mathcal{B}}|\mathcal{A}^{\prime}|+|\mathcal{B}^{ \prime}|\quad\mathrm{s.t.}\quad\mathcal{A}^{\prime}\text{ and }\mathcal{B}^{\prime}\text{ are linearly separable}.\]

Namely, \(\mathrm{MaxLS}(\mathcal{A},\mathcal{B})\) is the largest-size subset of \(\mathcal{A}\cup\mathcal{B}\) such that \(\mathcal{A}_{\circ}\) and \(\mathcal{B}_{\circ}\) are linearly separable. It is noteworthy that \(\mathrm{MaxLS}(\mathcal{A},\mathcal{B})\) could not be unique.

**Remark 6**.: _The maximum linearly-separable subset \(\mathrm{MaxLS}(\mathcal{A},\mathcal{B})\) of two sets \(\mathcal{A}\) and \(\mathcal{B}\) can be obtained in an iterative way: (1) Given \(P\times Q\) points \(\mathbf{m}_{i_{1},j_{1}},\cdots,\mathbf{m}_{i_{P},j_{Q}}\) lie in the minor side of

Figure 1: The workflow of obtaining the maximum linearly separable subset. Left: two point sets with the marks that signify the one to be removed in the iterations. Middle: two convex hulls of the rest points in the two sets. Right: Minkowski difference of the rest points
\(\mathbf{\omega}^{T}\mathbf{m}=0\), build a undirected bipartite graph \(G(\mathcal{V}_{0},\mathcal{E}_{0})\) with \(\mathcal{V}_{0}=\{\mathbf{a}_{i_{1}},\cdots,\mathbf{a}_{i_{P}},\mathbf{b}_{j_{1} },\cdots,\mathbf{b}_{j_{Q}}\}\) and \(\mathcal{E}=\{(\mathbf{a}_{i_{1}},\mathbf{b}_{j_{1}}),\cdots,(\mathbf{a}_{i_{ P}},\mathbf{b}_{j_{Q}})\}\). (2) Remove one vertex \(v_{1}\) with the largest degree from \(\mathcal{V}_{0}\) and update \(\mathcal{V}_{1}=\mathcal{V}_{0}\setminus\{v_{1}\}\). (3) Eliminate the edges associated with the vertex \(v_{1}\) and update \(\mathcal{E}_{1}\leftarrow\mathcal{E}_{0}\). (4) Repeat the steps (2)-(3) until \(\mathcal{E}_{t}=\emptyset\). (5) Remove the points in \(\mathcal{V}_{0}\setminus\mathcal{V}_{t}\) from the original sets \(\mathcal{A}\) and \(\mathcal{B}\), and the rest form the desired \(\mathrm{MaxLS}(\mathcal{A},\mathcal{B})\). Figure 1 exhibits a numerical example of this algorithm as well._

### MD-based Linear Separability Measure (MD-LSM)

Following Theorem 3, the ratio of the numbers of the points \(\mathbf{m}_{ij}\in\mathrm{MD}(\mathcal{A},\mathcal{B})\) that respectively locate in the two sides of the hyperplane can be treated as a criterion to measure the linear separability degree between \(\mathcal{A}\) and \(\mathcal{B}\):

\[\mathrm{LS}_{*}(\mathcal{A},\mathcal{B}):=\max_{\mathbf{\omega}\in \mathbb{R}^{N}}\left\{\max\left\{\frac{\sum\limits_{i\leq I,j\leq J}\mathbf{1} (\mathbf{\omega}^{T}\mathbf{m}_{ij}>0)}{|\mathrm{MD}(\mathcal{A},\mathcal{B})|}, \frac{\sum\limits_{i\leq I,j\leq J}\mathbf{1}(\mathbf{\omega}^{T}\mathbf{m}_{ij}<0 )}{|\mathrm{MD}(\mathcal{A},\mathcal{B})|}\right\}\right\}, \tag{1}\]

where \(|\mathrm{MD}(\mathcal{A},\mathcal{B})|\) is the cardinality of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) and \(\mathbf{1}(\mathcal{E})\) is the indicator function w.r.t. the event \(\mathcal{E}\). Denote \(\mathrm{ACC}_{\mathbf{w},\mathbf{b}}(\mathcal{A},\mathcal{B})\) as the classification accuracy of the linear model \(\mathbf{y}=\langle\mathbf{w},\mathbf{x}\rangle+\mathbf{b}\) on the point sets \(\mathcal{A}\cup\mathcal{B}\), and denote \(\mathrm{ACC}_{\mathrm{line}}(\mathcal{A},\mathcal{B}):=\max_{\mathbf{w}, \mathbf{b}\in\mathbb{R}^{N}}\{\mathrm{ACC}_{\mathbf{w},\mathbf{b}}(\mathcal{A },\mathcal{B})\}\) as the maximum classification accuracy of all possible linear models. The following theorem illustrates the relationship between \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\) and the maximum linearly separable subsets:

**Theorem 7**.: _Given two point sets \(\mathcal{A}\) and \(\mathcal{B}\), then_

\[\mathrm{ACC}_{\mathrm{line}}(\mathcal{A},\mathcal{B})=\frac{|\mathcal{A}_{0}|+ |\mathcal{B}_{0}|}{|\mathcal{A}|+|\mathcal{B}|}\geq\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\geq\max\left\{\frac{|\mathcal{A}_{0}|}{|\mathcal{A}|},\frac{| \mathcal{B}_{0}|}{|\mathcal{B}|}\right\},\]

_and the equality holds if and only if the sets \(\mathcal{A}\) and \(\mathcal{B}\) are linearly separable._

This result also reveals that the relationship between the linear separability and the classification accuracy of linear models. Although the classification accuracy can be used to evaluate the performance of a network, it is still challenging to track the behavior of each hidden layer during its training phase. This theorem provides a way of evaluating the linear separability of the outputs of each hidden layer during the training phase.

### Computation of MD-LSM

Since the computation of \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\) is NP-hard, we consider a variant of \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\):

\[\mathrm{LS}_{0}(\mathcal{A},\mathcal{B}):=\max_{\mathbf{\omega}\in \mathbb{R}^{N}}\left\{\max\left\{\frac{\sum\limits_{i\leq I,j\leq J}\mathrm{ sgn}(\mathbf{\omega}^{T}\mathbf{m}_{ij})}{|\mathrm{MD}(\mathcal{A},\mathcal{B})|}, \frac{\sum\limits_{i\leq I,j\leq J}\mathrm{sgn}(-\mathbf{\omega}^{T}\mathbf{m}_{ ij})}{|\mathrm{MD}(\mathcal{A},\mathcal{B})|}\right\}\right\}, \tag{2}\]

where \(\mathrm{sgn}(\cdot)\) is a sign function. The following lemma demonstrates that \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\) and \(\mathrm{LS}_{0}(\mathcal{A},\mathcal{B})\) are equivalent from the perspective of maximum linearly separable subset:

**Lemma 8**.: _Given two sets \(\mathcal{A},\mathcal{B}\), let \(\mathbf{\omega}_{*}\) and \(\mathbf{\omega}_{0}\) be the weight vectors achieving the maximum operations in (1) and (2), respectively. Then, it holds that \(\mathrm{major}_{\mathbf{\omega}_{*}}(\mathrm{MD}(\mathcal{A},\mathcal{B}))=\mathrm{ major}_{\mathbf{\omega}_{0}}(\mathrm{MD}(\mathcal{A},\mathcal{B}))\)._
The proof of this lemma is direct, so we omit it here. It shows that the points lying in the major sides of the two hyperplanes \(\mathbf{\omega}_{*}^{T}\mathbf{m}=0\) and \(\mathbf{\omega}_{0}^{T}\mathbf{m}=0\) are the same. Unfortunately, it is still NP-hard to solve the optimization problem (2). Instead, we consider the following term:

\[\text{LS}_{1}(\mathcal{A},\mathcal{B}):=\max_{\mathbf{\omega}\in\mathbb{R}^{N}} \left\{\left|\sum_{i\leq I,j\leq J}\mathbf{\omega}^{T}\mathbf{m}_{ij}\right|\!\! \middle/\sum_{i\leq I,j\leq J}\left|\mathbf{\omega}^{T}\mathbf{m}_{ij}\right|\right\}. \tag{3}\]

The numerator \(|\sum_{i,j}\mathbf{\omega}^{T}\mathbf{m}_{ij}|\) is the absolute value of the sum of the directed distances from the points of \(\text{MD}(\mathcal{A},\mathcal{B})\) to the hyperplane \(\mathbf{\omega}^{T}\mathbf{m}=0\). If all points of \(\text{MD}(\mathcal{A},\mathcal{B})\) locate in one side of \(\mathbf{\omega}^{T}\mathbf{m}=0\), _i.e.,_ the two sets \(\mathcal{A},\mathcal{B}\) are linearly separable, it holds that \(\text{LS}_{1}(\mathcal{A},\mathcal{B})=1\). In contrast, if the value of \(\text{LS}_{1}(\mathcal{A},\mathcal{B})\) is close to zero, the convex hulls of the two sets \(\mathcal{A},\mathcal{B}\) overlap heavily.

Because of the existence of absolute value operation, it is still difficult to solve the optimization problem (3). Thus, we consider its alternative version:

\[\text{LS}_{2}(\mathcal{A},\mathcal{B}):=\max_{\mathbf{\omega}\in\mathbb{R}^{N}} \left\{\left(\sum_{i\leq I,j\leq J}\mathbf{\omega}^{T}\mathbf{m}_{ij}\right)^{2} \middle/\sum_{i\leq I,j\leq J}\left(\mathbf{\omega}^{T}\mathbf{m}_{ij}\right)^{2} \right\}. \tag{4}\]

Let \(\widetilde{\mathbf{m}}:=\sum_{i\leq I,j\leq J}\mathbf{m}_{ij}\) be the sum of all points of \(\text{MD}(\mathcal{A},\mathcal{B})\) and define

\[\mathbf{M}=[\mathbf{m}_{11},\cdots,\mathbf{m}_{1J},\cdots,\mathbf{m}_{i1}, \cdots,\mathbf{m}_{iJ},\cdots,\mathbf{m}_{I1},\cdots,\mathbf{m}_{IJ}]_{N\times IJ}\]

as the matrix with the points of \(\text{MD}(\mathcal{A},\mathcal{B})\) being its column vectors. Then, the optimization problem (4) can be rewritten as

\[\text{LS}_{2}(\mathcal{A},\mathcal{B})=\max_{\mathbf{\omega}\in\mathbb{R}^{N}} \left\{\frac{\mathbf{\omega}^{T}\widetilde{\mathbf{m}}\widetilde{\mathbf{m}}^{T} \mathbf{\omega}}{\mathbf{\omega}^{T}\mathbf{MM}^{T}\mathbf{\omega}}\right\}, \tag{5}\]

which has an equivalent form:

\[\max_{\mathbf{\omega}\in\mathbb{R}^{N}}\ \ \mathbf{\omega}^{T}\widetilde{\mathbf{m}} \widetilde{\mathbf{m}}^{T}\mathbf{\omega}\ \ \ \text{s.t.}\ \ \ \mathbf{\omega}^{T}\mathbf{MM}^{T}\mathbf{\omega}=1\ \ \ \Longleftrightarrow\ \ \max_{\overline{\mathbf{\omega}}\in\mathbb{R}^{N}}\ \ \overline{\mathbf{\omega}}^{T}\mathbf{\Sigma}\overline{\mathbf{\omega}}\ \ \ \text{s.t.}\ \ \ \overline{\mathbf{\omega}}^{T}\overline{\mathbf{\omega}}=1, \tag{6}\]

where \(\mathbf{\Sigma}:=(\mathbf{MM}^{T})^{-\frac{1}{2}}\widetilde{\mathbf{m}}\widetilde{ \mathbf{m}}^{T}(\mathbf{MM}^{T})^{-\frac{1}{2}}\) and \(\overline{\mathbf{\omega}}:=(\mathbf{MM}^{T})^{1/2}\mathbf{\omega}\). Then, \(\text{LS}_{2}(\mathcal{A},\mathcal{B})\) should be the largest eigenvalue of \(\mathbf{\Sigma}\) and the solution \(\widehat{\mathbf{\omega}}=(\mathbf{MM}^{T})^{-\frac{1}{2}}\overline{\mathbf{\omega}}^ {\dagger}\), where \(\overline{\mathbf{\omega}}^{\dagger}\) is the eigenvector associated with the largest eigenvalue of \(\mathbf{\Sigma}\). Then, we obtain a closed form of the solution to (4). Furthermore, the resultant \(\widehat{\mathbf{\omega}}\) will be substituted into Eqs. (1)-(3) to achieve the approximate calculation of the MD-LSMs LS\({}_{*}\), LS\({}_{0}\) and LS\({}_{1}\), respectively. We note that, in the case of large sample size or high network width or both of them, it is still time-consuming to perform the eigenvalue decomposition on the hidden-layer outputs \(\text{hid}(\mathcal{X})\) after each time of updating network weights. Thus, we adopt a more efficient way to obtain the approximate values of LS\({}_{*}\), LS\({}_{0}\), LS\({}_{1}\) and LS\({}_{2}\) in the subsequent numerical experiments (_cf._ Remark 15).

In addition, we present a theorem to show that the linear transformation cannot effect the linear separability of original point sets:

**Theorem 9** (Linear Transformation).: _Let \(\mathcal{A}=\{\mathbf{a}_{1},\cdots,\mathbf{a}_{I}\}\subset\mathbb{R}^{N}\) and \(\mathcal{B}=\{\mathbf{b}_{1},\cdots,\mathbf{b}_{J}\}\subset\mathbb{R}^{N}\) be two point sets. Denote \(\mathbf{V}=[\mathbf{v}_{1},\cdots,\mathbf{v}_{H}]_{N\times H}\) as the weight matrix, where \(\mathbf{v}_{h}=(v_{h1},\cdots,v_{hN})^{T}\in\mathbb{R}^{N}\). Define \(\mathbf{V}(\mathcal{A})=\{\mathbf{V}^{T}\mathbf{a}_{i}:1\leq i\leq I\}\) and \(\mathbf{V}(\mathcal{B})=\{\mathbf{V}^{T}\mathbf{b}_{j}:1\leq j\leq J\}\). Then, it holds that \(\text{LS}_{i}(\mathcal{A},\mathcal{B})=\text{LS}_{i}(\mathbf{V}(\mathcal{A}), \mathbf{V}(\mathcal{B}))\) (\(i=*,0,1,2\))._
This theorem demonstrates that the linear transformation \(\mathbf{V}(\mathbf{x})=\mathbf{V}^{T}\mathbf{x}\) cannot change the linear separability degree of the original point sets. Therefore, it is necessary to equip the nodes of hidden layers with non-linear activation functions. At the end of this section, we define the MD-LSMs for multiple point sets:

**Definition 10** (MD-LSMs for Multi-class Classification).: _Given \(S\) point sets \(\mathcal{A}_{1},\cdots,\mathcal{A}_{S}\), denote \(\mathcal{A}_{s}^{c}=\bigcup_{t\in\{1,\cdots,S\}\setminus\{s\}}\mathcal{A}_{t}\). Then, the MD-LSM for the \(S\) points sets is defined as:_

\[\mathrm{MultiLS}_{i}\big{(}\mathcal{A}_{1},\cdots,\mathcal{A}_{S}\big{)}=\sum _{s=1}^{S}\frac{|\mathcal{A}_{s}|\cdot\mathrm{LS}_{i}(\mathcal{A}_{s}, \mathcal{A}_{s}^{c})}{\sum_{s=1}^{S}\big{|}\mathcal{A}_{s}\big{|}},\quad i=*,0, 1,2.\]

In the one-vs-rest (OvR) way, we break down an \(S\)-class classification task into \(S\) binary classification tasks and then compute the individual \(\mathrm{LS}_{i}(\mathcal{A}_{s},\mathcal{A}_{s}^{c})\) of each task. Then, the MD-LSM \(\mathrm{MultiLS}_{i}\big{(}\mathcal{A}_{1},\cdots,\mathcal{A}_{S}\big{)}\) of the \(S\)-class sample sets is expressed as a sum of \(\mathrm{LS}_{i}(\mathcal{A}_{s},\mathcal{A}_{s}^{c})\) weighted by the ratio of the size of \(\mathcal{A}_{s}\) to the size of all samples.

## 3 Effects of Activation Function and Network Size

In this section, we study the effects of activation function and network size on the linear separability degree of hidden layer outputs.

### Activation Functions

Consider a hidden layer of a neural network that contains \(H\) hidden nodes, and let \(\sigma:\mathbb{R}\rightarrow\mathbb{R}\) be an activation function. Given an input \(\mathbf{x}=(x_{1},\cdots,x_{N})^{T}\in\mathbb{R}^{N}\), denote \(\mathbf{V}=[\mathbf{v}_{1},\cdots,\mathbf{v}_{H}]_{N\times H}\) as the weight matrix, where \(\mathbf{v}_{h}=(v_{h1},\cdots,v_{hN})^{T}\in\mathbb{R}^{N}\) is the weight vector between the input and the \(h\)-th hidden node. Then, the hidden layer of neural networks can be regarded as a pseudo-linear mapping (PLM) in the following form:

\[\mathbf{V}_{\sigma}(\mathbf{x}):=\left(\sigma(\langle\mathbf{v}_{1},\mathbf{x }\rangle),\cdots,\sigma(\langle\mathbf{v}_{H},\mathbf{x}\rangle)\right)^{T}.\]

Especially, if \(\mathbf{V}\) is a random matrix, the mapping \(\mathbf{V}_{\sigma}(\mathbf{x})\) is called the random PLM accordingly. Denote \(\mathrm{MD}(\mathbf{V}_{\sigma}(\mathcal{A}),\mathbf{V}_{\sigma}(\mathcal{B}) )=\{\mathbf{n}_{ij}:=\mathbf{V}_{\sigma}(\mathbf{a}_{i})-\mathbf{V}_{\sigma} (\mathbf{b}_{j})\mid 1\leq i\leq I,\ 1\leq j\leq J\}\) as the Minkowski difference of two transformed sets \(\mathbf{V}_{\sigma}(\mathcal{A})\) and \(\mathbf{V}_{\sigma}(\mathcal{B})\). The following theorem shows that PLMs have the capability of changing the linear separability of the original point sets \(\mathcal{A}\) and \(\mathcal{B}\).

**Theorem 11**.: _Let \(\mathbf{V}_{\sigma}:\mathbb{R}^{N}\rightarrow\mathbb{R}^{H}\) be a pseudo-linear mapping and \(\sigma(x):\mathbb{R}\rightarrow\mathbb{R}\) be a second order derivable function with non-negative first derivative. Assume that an MD point \(\mathbf{m}_{ij}=\mathbf{a}_{i}-\mathbf{b}_{j}\) lies in the major (resp. minor) side of the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\). Define_

\[F_{\sigma}(x,y):=\frac{\big{[}\sigma^{\prime\prime}(x)-\sigma^{\prime\prime}(y )\big{]}(x-y)}{\big{[}\sigma^{\prime}(x)+\sigma^{\prime}(y)\big{]}},\ \ (x,y)\in\mathbb{R}\times \mathbb{R}.\]

_If the relation \(F_{\sigma}(\langle\mathbf{a}_{i},\mathbf{v}_{h}\rangle,\langle\mathbf{b}_{j}, \mathbf{v}_{h}\rangle)>2\) holds for any \(h\in\{1,2,\cdots,H\}\), then the MD point \(\mathbf{n}_{ij}=\mathbf{V}_{\sigma}(\mathbf{a}_{i})-\mathbf{V}_{\sigma}( \mathbf{b}_{j})\) lies in the minor (resp. major) side of the hyperplane \((\boldsymbol{\omega}^{T}\mathbf{V})\mathbf{n}=0\)._

This result interprets that if the weights \(\mathbf{v}_{1},\cdots,\mathbf{v}_{H}\) satisfy that \(F_{\sigma}(\langle\mathbf{a}_{i},\mathbf{v}_{h}\rangle,\langle\mathbf{b}_{j}, \mathbf{v}_{h}\rangle)>2\) for any \(h\in\{1,2,\cdots,H\}\), the MD point \(\mathbf{n}_{ij}\) has a different relatively positional relation with the hyperplane \((\boldsymbol{\omega}^{T}\mathbf{V})\mathbf{n}=0\). In other words, if the original MD point \(\mathbf{m}_{ij}\) lies in the major side of \(\boldsymbol{\omega}^{T}\mathbf{m}=0\), the
transformed MD point \(\mathbf{n}_{ij}\) lies in the minor side of \((\mathbf{\omega}^{T}\mathbf{V})\mathbf{n}=0\). As shown in Fig. 2, there is a wide choice of the activation function \(\sigma\), such as sigmoid, \(\tanh\), \(\arctan\) and softsign.

### Network Size

By treating the multiple hidden layers as the composition of multiple PLMs, we consider the effect of the network size (including width and depth) on the linear separability. Denote

\[\mathbf{V}_{\sigma}^{L}(\mathbf{a}):=\prod_{l=1}^{L}\mathbf{V}_{\sigma}^{(l)}( \mathbf{a})=\mathbf{V}_{\sigma}^{(L)}\circ\mathbf{V}_{\sigma}^{(L-1)}\circ \cdots\circ\mathbf{V}_{\sigma}^{(1)}(\mathbf{a}),\]

where \(\mathbf{V}_{\sigma}^{(1)},\cdots,\mathbf{V}_{\sigma}^{(L)}\) are independent random PLMs with \(\mathbf{V}^{(l)}\in\mathbb{R}^{H_{l-1}\times H_{l}}\), and the operation \(\circ\) stands for the composition of two PLMs. Denote \(\mathbf{V}_{\sigma}^{L}(\mathcal{A})=\{\mathbf{V}_{\sigma}^{L}(\mathbf{a}): \mathbf{a}\in\mathcal{A}\}\) as the set of the \(L\)-th hidden layer outputs w.r.t. the input set \(\mathcal{A}\). For any \(1\leq l\leq L\), let

\[\mathrm{MD}(\mathbf{V}_{\sigma}^{(l)}(\mathcal{A}),\mathbf{V}_{\sigma}^{(l)} (\mathcal{B})):=\{\mathbf{n}_{ij}^{(l)}:=\mathbf{V}_{\sigma}^{(l)}(\mathbf{a }_{i})-\mathbf{V}_{\sigma}^{(l)}(\mathbf{b}_{j})\mid 1\leq i\leq I,\;1\leq j \leq J\}\]

be the Minkowski difference of two transformed sets \(\mathbf{V}_{\sigma}^{(l)}(\mathcal{A})\) and \(\mathbf{V}_{\sigma}^{(l)}(\mathcal{B})\). Let \(\widetilde{\mathbf{n}}^{(l)}=\sum_{i\leq I,j\leq J}\mathbf{n}_{ij}^{(l)}\) be the sum of all hidden-layer outputs and \(\mathbf{N}^{(l)}=[\mathbf{n}_{1}^{(l)},\cdots,\mathbf{n}_{IJ}^{(l)}]_{H_{l} \times(IJ)}\) be the matrix with the points of \(\mathrm{MD}(\mathbf{V}_{\sigma}^{(l)}(\mathcal{A}),\mathbf{V}_{\sigma}^{(l)} (\mathcal{B}))\) being its column vectors. For any \(1\leq l\leq L\), set

\[\mathbf{\Omega}^{(l)}:=[\mathbf{N}^{(l)}(\mathbf{N}^{(l)})^{T}]^{-\frac{1}{2}} \widetilde{\mathbf{n}}^{(l)}(\widetilde{\mathbf{n}}^{(l)})^{T}[\mathbf{N}^{( l)}(\mathbf{N}^{(l)})^{T}]^{-\frac{1}{2}}.\]

Some empirical evidences have shown that if the number of hidden nodes is larger than the dimension of the original data, the linear separability degree of the hidden layer outputs is likely to be larger than that of the original data. By using Tropp's tail inequality for random matrices [45, Theorem 1.3], we study the relationship between the linear separability and the number of hidden nodes:

**Theorem 12** (Network Width).: _If \(\mathbb{E}\mathbf{\Omega}^{(1)}=0\) and \((\mathbf{\Omega}^{(1)})^{2}\preceq\mathbf{A}^{2}\), then_

\[\mathbb{P}\{\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{(1)}(\mathcal{A}),\mathbf{V }_{\sigma}^{(1)}(\mathcal{B}))>\mathrm{LS}_{2}(\mathcal{A},\mathcal{B})\}\leq H \cdot\mathrm{e}^{-\frac{(\mathrm{LS}_{2}(\mathcal{A},\mathcal{B}))^{2}}{8 \sigma^{2}}}, \tag{7}\]

_where \(\sigma^{2}:=\|\mathbf{A}^{2}\|_{s}\), \(\mathbf{A}\preceq\mathbf{B}\) means that \(\mathbf{B}-\mathbf{A}\) is a positive semidefinite matrix and \(\|\cdot\|_{s}\) stands for the spectral norm._

This result addresses that with probability at most \(H\mathrm{e}^{-(\mathrm{LS}_{2}(\mathcal{A},\mathcal{B}))^{2}/8\sigma^{2}}\), the value of \(\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{(1)}(\mathcal{A}),\mathbf{V}_{\sigma}^{( 1)}(\mathcal{B}))\) is larger than that of \(\mathrm{LS}_{2}(\mathcal{A},\mathcal{B})\). Namely, if we would like to improve the linear separability degree

Figure 2: The ranges of \(F_{\sigma}(x,y)\) for different activation functions.
of the original sets \(\mathcal{A}\) and \(\mathcal{B}\), one feasible way is to map them into a higher-dimensional space via non-linear mappings, _i.e.,_ to increase the network width. Moreover, if the linear separability degree of \(\mathcal{A}\) and \(\mathcal{B}\) reaches a relatively high level, the probability that the random PLM \(\mathbf{V}_{\sigma}^{(1)}(\cdot)\) can further improve their linear separability degree becomes low.

**Corollary 13** (Network Depth).: _Assume that \(\mathbb{E}\mathbf{\Omega}^{(l)}=0\) and \((\mathbf{\Omega}^{(l)})^{2}\preceq(\mathbf{A}^{(l)})^{2}\) holds for any \(1\leq l\leq L\). Then,_

\[\mathbb{P}\{\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{L}(\mathcal{A}),\mathbf{V}_{ \sigma}^{L}(\mathcal{B}))>\mathrm{LS}_{2}(\mathcal{A},\mathcal{B})\}\leq LH \cdot\mathrm{e}^{-C_{0}^{2}/(8\sigma_{0}^{2})}, \tag{8}\]

_where \(\sigma_{0}^{2}=\max_{l}\|(\mathbf{A}^{(l)})^{2}\|_{s}\) and \(C_{0}:=\min_{l}\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{(l)}(\mathcal{A}),\mathbf{ V}_{\sigma}^{(l)}(\mathcal{B}))\)._

This result suggests that adding more hidden layers is also a feasible way to increase the linear separability degree of the data points when they pass through a neural network.

**Remark 14**.: _We note that the results (7) and (8) are not of the optimal forms. For example, it is expected to find a monotonically decreasing function \(\rho(H)\) w.r.t. the network width \(H\) such that_

\[\mathbb{P}\big{\{}\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{(1)}( \mathcal{A}),\mathbf{V}_{\sigma}^{(1)}(\mathcal{B}))\leq\mathrm{LS}_{2}( \mathcal{A},\mathcal{B})\big{\}}\leq\rho(H), \tag{9}\]

_which can be equivalently interpreted as follows: with probability at least \(1-\rho(H)\), it holds that \(\mathrm{LS}_{2}(\mathbf{V}_{\sigma}^{(1)}(\mathcal{A}),\mathbf{V}_{\sigma}^{( 1)}(\mathcal{B}))>\mathrm{LS}_{2}(\mathcal{A},\mathcal{B})\). Unfortunately, it is still technically difficult to obtain the appropriate small-ball probability inequalities for the largest eigenvalues of random matrices to achieve the probability inequality of the form (9)._

## 4 Numerical Experiments

In this section, we conduct the experiments to examine the synchronicity between the linear separability degree of hidden layer outputs and the network training performance of several popular networks including MLP, CNN, DBN, ResNet-20, VGGNet, AlexNet, ViT and GoogLeNet-V1. The experimental results also validate the theoretical findings in Theorem 12 and Corollary 13. All experiments are processed in the DELL(r) PowerEdge(r) T640 Tower Server with two Intel(r) Xeon(r) 20-core processors, 128 GB RAM and a NVIDIA(r) Tesla(r) V100 32GB GPU.

### Experiment Setting

Two categories (airplane and automobile) in CIFAR-10 dataset [46] are selected to form the binary classification task. The SGD method with minibatch is used to updated the network weights within 100 training epochs (including the fine-tuning phase of DBN). Since the structures of MLP, CNN and DBN are not powerful enough to obtain a good training performance by using all samples of the two categories within the limited epochs, we randomly select 2000 (resp. 1000) samples from the training (resp. testing) data of the two categories for training (resp. testing) the three kinds of networks. Moreover, since the network size of MLP, CNN and DBN is not large, we directly use the selected 2000 training samples to compute the MD-LSMs of their hidden layer outputs. In contrast, we use all training (resp. testing) data of the two categories to train (resp. test) ResNet, VGGNet, AlexNet, ViT and GoogLeNet. Since the dimension of hidden layer outputs of these deep networks is high, in view of the computational burden, we randomly select 500 samples from the two categories to compute MD-LSMs for these networks after each training epoch.
Figure 3: Synchronicity between the LS\({}_{1}\) value (the left of each subfigure) of hidden layer outputs and training (or testing) accuracy (the right of each subfigure) of different neural networks, where L1 and B1 stand for the 1st hidden layer and the 1st block, respectively. Since the ranges of LS\({}_{1}\), training accuracy and testing accuracy are all the interval \([0,1]\), the corresponding curves share the same \(y\) label in each subfigure.
**Remark 15** (Approximate Calculation of MD-LSMs).: _Recall the optimization problem (6) for computing \(\mathrm{LS}_{2}\). Unfortunately, it is still very time-consuming to implement the eigenvalue decomposition of \(\mathbf{\Sigma}\) after each training epoch, especially when the dimension of \(\mathbf{\Sigma}\) is high. Thus, in the numerical experiments, the weight vectors achieving the MD-LSMs (1), (2), (3) and (4) are approximately computed after each training epoch via the following optimization problem:_

\[\max_{\mathbf{\omega}\in\mathbb{R}^{N}}\ \mathbf{\omega}^{T}\widetilde{\mathbf{m}} \widetilde{\mathbf{m}}^{T}\mathbf{\omega}\quad\text{s.t.}\quad\mathbf{\omega}^{T}\mathbf{ \omega}=1, \tag{10}\]

_whose solution is \(\widehat{\mathbf{\omega}}=\frac{\widetilde{\mathbf{m}}}{\|\widetilde{\mathbf{m}} \|}\). Compared with the original form (6), this approximate one actually is derived by setting \(\mathbf{M}\mathbf{M}^{T}=\mathbf{I}\)._

### Experimental Results and Discussion

In Fig. 3, we illustrate the synchronicity between linear separability of hidden layers and training performance in the classification tasks. Since \(\mathrm{LS}_{0}\), \(\mathrm{LS}_{1}\) and \(\mathrm{LS}_{2}\) basically have the same experimental results, we only draw the \(\mathrm{LS}_{1}\) curves for all hidden layers of MLP, CNN and DBN and for the main blocks of AlexNet, GoogLeNet, ResNet, VGGNet and ViT, respectively. The complete experimental report, containing \(\mathrm{LS}_{0}\), \(\mathrm{LS}_{1}\) and \(\mathrm{LS}_{2}\) curves for all hidden layers of these networks, is arranged in the appendix (part B). Moreover, we also provide the detailed structures of these neural networks with the name of each hidden layer to facilitate the interpretation of experimental results.

**[Binary Classification]** As shown in Figs. 3(a)-3(j), there is an obvious synchronicity between the \(\mathrm{LS}_{1}\) curves of hidden layers and the accuracy curves: 1) when the training accuracy increases, the \(\mathrm{LS}_{1}\) value of the outputs of each hidden layer (or main block) increases synchronously; 2) when some fluctuations appear in the \(\mathrm{LS}_{1}\) curves, the training and the testing accuracy curves have the fluctuations occurring nearby the corresponding epochs accordingly; 3) especially for the neural networks with relatively shallow structures, such as MLP and CNN (_cf._ Figs. 3(a)-3(e)), the magnitude of the fluctuations in the \(\mathrm{LS}_{1}\) curves is merely proportional to that of the fluctuations in the training and the testing accuracy curves.

**[Network Size]** The experimental results, given in Figs. 3(a)-3(k), also reflect two facts: 1) in most cases, the linear separability of the hidden layers (or blocks) is stronger than that of the original data after a few training epochs; and 2) the hidden layers (or blocks), which are closer to the output layer, have higher linear separability. These phenomena coincide with the theoretical findings in Theorem 12 and Corollary 13, which have proven that the large network size is more likely to provide high linear separability of the hidden layers.

**[Multi-class Classification]** We also consider the linear separability of MLP for ten-class classification task. The experiment is conducted by using MLP to classify the MINST dataset [32]. We adopt the one-vs-rest (OvR) way to build ten MLPs with the same structure. After each training epoch, we compute the MD-LSMs of all hidden layer outputs of each CNN in the way mentioned in Definition 10. As shown in Fig. 3(k), we obtain the same experiment observations as binary classification tasks and support the theoretical findings as well.

**[Layer-wise Pretraining]** We use the linear separability to analyze the layer-wise pretraining strategy, implemented by using restricted Boltzmann machine (RBM), of DBN in binary classification task. During the pretraining phase, the weights of each hidden layers are updated 100 times. After that, all weights of the network are fine-tuned in 100 epochs by using the SGD method. RBM is an energy minimization method and the layer-wise pretraining aims to find the suitable weights such that the energy between two adjacent hidden layers decays to the minimal status. As shown in Fig. 17, the RBM-based pretraining not only fails to increase the linear separability degree of each
hidden layer but also makes it lower than the original data. However, the subsequent fine-tuning process can quickly improve the linear separability of hidden layers and meanwhile the network achieves a good performance. This phenomenon implies that the RBM-based pretraining makes each hidden layer capture useful features, which are not beneficial to increasing the linear separability degree yet. The reason is that the RBM method is independent of the label information, while the evaluation of linear separability is label-based. Interestingly, during the pretraining phase, the training and the testing accuracies are both round the value of 0.5. This phenomenon implies that the network always maintains the largest randomness and diversity, which will benefit to the subsequent fine-tuning process.

## 5 Difference between MD-LSM and Fisher LDA

In this section, we make a comparison between \(\text{LS}_{2}(\mathcal{A},\mathcal{B})\) and Fisher LDA. First, we present a theorem to show their differences, and then explain why we use MD-LSM to evaluate the linear separability degree of two sets instead of Fisher LDA.

Let \(\boldsymbol{\mu}_{a}=\frac{1}{I}\sum_{i=1}^{I}\mathbf{a}_{i}\) and \(\boldsymbol{\mu}_{b}=\frac{1}{J}\sum_{j=1}^{J}\mathbf{b}_{j}\) be the centers of the sets \(\mathcal{A}\) and \(\mathcal{B}\), respectively. Let \(\mathbf{A}_{c}\) (resp. \(\mathbf{B}_{c}\)) be the matrix associated with the set \(\mathcal{A}\) (resp. \(\mathcal{B}\)) whose columns consist of the mean shifted data points:

\[\mathbf{A}_{c}:=[\mathbf{a}_{1}-\boldsymbol{\mu}_{a},\cdots,\mathbf{a}_{I}- \boldsymbol{\mu}_{a}]\;\;\text{and}\;\;\mathbf{B}_{c}:=[\mathbf{b}_{1}- \boldsymbol{\mu}_{b},\cdots,\mathbf{b}_{J}-\boldsymbol{\mu}_{b}].\]

Denote \(\mathbf{S}_{w}=\mathbf{A}_{c}\mathbf{A}_{c}^{T}+\mathbf{B}_{c}\mathbf{B}_{c}^ {T}\) and \(\mathbf{S}_{b}=(\boldsymbol{\mu}_{a}-\boldsymbol{\mu}_{b})(\boldsymbol{\mu}_{a }-\boldsymbol{\mu}_{b})^{T}\). The objective function of Fisher LDA can also be treated as an LSM:

\[J_{\omega}=\max_{\boldsymbol{\omega}}\frac{\boldsymbol{\omega}^{T}\mathbf{S}_{ b}\boldsymbol{\omega}}{\boldsymbol{\omega}^{T}\mathbf{S}_{w}\boldsymbol{\omega}}. \tag{11}\]

The following results show the difference between MD-LSM and LDA-LSM.

**Proposition 16**.: _Given two point sets \(\mathcal{A}=\{\mathbf{a}_{1},\cdots,\mathbf{a}_{I}\}\) and \(\mathcal{B}=\{\mathbf{b}_{1},\cdots,\mathbf{b}_{J}\}\), then it holds that_

\[I^{2}J^{2}\mathbf{S}_{b} = \widetilde{\mathbf{m}}\widetilde{\mathbf{m}}^{T};\] \[\mathbf{S}_{w} = \mathbf{A}\mathbf{A}^{T}+\mathbf{B}\mathbf{B}^{T}-\Big{(}I( \widehat{\mathbb{E}}\mathbf{a})(\widehat{\mathbb{E}}\mathbf{a})^{T}+J( \widehat{\mathbb{E}}\mathbf{b})(\widehat{\mathbb{E}}\mathbf{b})^{T}\Big{)};\] \[\mathbf{M}\mathbf{M}^{T} = J\mathbf{A}\mathbf{A}^{T}+I\mathbf{B}\mathbf{B}^{T}-IJ\cdot \widehat{\mathbb{E}}\{\mathbf{a}\mathbf{b}^{T}+\mathbf{b}\mathbf{a}^{T}\},\]

_where \(\widehat{\mathbb{E}}\) stands for the sample mean with_

\[\widehat{\mathbb{E}}\mathbf{a} = \frac{1}{I}\sum_{i=1}^{I}\mathbf{a}_{i};\] \[\widehat{\mathbb{E}}\mathbf{b} = \frac{1}{J}\sum_{j=1}^{J}\mathbf{b}_{j};\] \[\widehat{\mathbb{E}}\{\mathbf{a}\mathbf{b}^{T}+\mathbf{b} \mathbf{a}^{T}\} = \frac{1}{IJ}\sum_{\begin{subarray}{c}1\leq i\leq I\\ 1\leq j\leq J\end{subarray}}(\mathbf{a}_{i}\mathbf{b}_{j}^{T}+\mathbf{b}_{j} \mathbf{a}_{i}^{T}).\]

As demonstrated above, since \(\mathbf{S}_{w}\) differs from \(\mathbf{M}\mathbf{M}^{T}\), the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\) achieving \(\text{LS}_{2}(\mathcal{A},\mathcal{B})\) is different from the one achieving \(J_{\omega}\). When we use the approximate way, mentioned in Remark 15, to compute the weight for the MD-LSMs, the corresponding optimization objective
function coincides with that of Fisher LDA with \(\mathbf{S}_{b}=\mathbf{I}\) (_cf._ Eq. (11)). In spite of the same weight vector \(\mathbf{\omega}\) derived from the approximated form, the linear separability degree is still evaluated in different forms after substituting \(\mathbf{\omega}\) into the expressions of MD-LSMs (including LS\({}_{*}\), LS\({}_{0}\), LS\({}_{1}\) and LS\({}_{2}\)) and \(J_{\omega}\), respectively.

Moreover, the ranges of LS\({}_{0}\) and LS\({}_{1}\) are the interval \((0,1]\); and LS\({}_{0}=\) LS\({}_{1}=1\) holds if and only if the two sets are linearly separable (_cf._ Fig. 4). In contrast, the ranges of LS\({}_{2}\) and \(J_{\omega}\) are the interval \((0,+\infty)\), and they only provide the relative reference values for the linear separability. Thus, it is difficult to estimate the linear separability degree of two sets only based on the values of LS\({}_{2}\) and \(J_{\omega}\). Moreover, as shown in Figs. 5 - 8, there are fewer large fluctuations appearing in the curves of LS\({}_{0}\) and LS\({}_{1}\) than in the curves of LS\({}_{2}\) and \(J_{\omega}\). Interestingly, the curve shapes of LS\({}_{0}\), LS\({}_{1}\) and LS\({}_{2}\) are the same, but they significantly differ from that of the curves of \(J_{\omega}\). Therefore, we finally adopt the MD-LSMs as the measures of evaluating the linear separability degree of hidden layer outputs.

## 6 Proofs of Main Results

In this section, we give the proofs of Theorem 1, Theorem 3, Theorem 7, Theorem 9, Theorem 11, Corollary 13 and Proposition 16, respectively.

### Proof of Theorem 1

**Proof of Theorem 1:** "\(\Longrightarrow\)" If the classification accuracy increases, it means that more hidden-layer outputs can be correctly separated by using a hyperplane \(\mathbf{w}^{T}\mathbf{x}+\mathbf{b}=0\). Namely, the linear separability of hidden layer outputs increases.

Figure 4: Evaluation of Linear Separability Degree of Different Point Sets Based on MD-LSMs and Fisher LDA.
Figure 5: Curves of MD-LSMs and \(J_{\omega}\) for Hidden Layers of MLP-5.

Figure 6: Curves of MD-LSMs and \(J_{\omega}\) for Hidden Layers of CNN
Figure 8: Curves of MD-LSMs and \(J_{\omega}\) for Hidden Layers of AlexNet (Sigmoid)

Figure 7: Curves of MD-LSMs and \(J_{\omega}\) for Hidden Layers of AlexNet (Softmax)
"\(\Longleftarrow\)" If the linear separability of the hidden layer outputs increases after updating the hidden-layer weights \(\mathbf{V}^{\prime}=\mathbf{V}+\triangle\mathbf{V}\), it means that there must exists a hyperplane \(\mathbf{w}^{\mathbf{T}}\mathbf{s}+\mathbf{b}=\mathbf{0}\) such that more hidden-layer outputs can be correctly separated. Since the hyperplane \((\mathbf{w}^{\prime})^{\mathbf{T}}\mathbf{s}+\mathbf{b}^{\prime}=\mathbf{0}\) can provide the highest training classification accuracy, the training performance of \(\mathrm{net}^{\prime}(\cdot)\) is better than that of \(\mathrm{net}(\cdot)\). This completes the proof. \(\blacksquare\)

### Proof of Theorem 3

**Proof of Theorem 3:** "\(\Longrightarrow\)": If \(\mathcal{A}\) and \(\mathcal{B}\) are linearly separable, there exists a vector \(\boldsymbol{\omega}\in\mathbb{R}^{N}\) and a constant \(c\in\mathbb{R}\) such that the relation \(\mathbf{w}^{T}\mathbf{a}+c>\mathbf{w}^{T}\mathbf{b}+c\) holds for all \(\mathbf{a}\in\mathcal{A}\) and \(\mathbf{b}\in\mathcal{B}\). Then, we arrive at \(\mathbf{w}^{T}(\mathbf{a}-\mathbf{b})>0\) (\(\forall\ \mathbf{a}\in\mathcal{A},\mathbf{b}\in\mathcal{B}\)). Namely, all points of the Minkowski difference \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) lie above the hyperplane \(\mathbf{w}^{T}\mathbf{x}=0\).

"\(\Longleftarrow\)": Assume that all points of \(\mathrm{MD}(\mathcal{A},\mathcal{B})\) lie in one side of the hyperplane \(\mathbf{w}^{T}\mathbf{x}=0\). Without loss of generality, we consider a vector \(\mathbf{w}\in\mathbb{R}^{N}\) such that \(\mathbf{w}^{T}(\mathbf{a}-\mathbf{b})>0\) holds for any \(\mathbf{a}\in\mathcal{A}\) and any \(\mathbf{b}\in\mathcal{B}\). Define \(\mathbf{a}^{*}:=\arg\min_{\mathbf{a}\in\mathcal{A}}\{\mathbf{w}^{T}\mathbf{a}\}\) and \(\mathbf{b}^{\dagger}:=\arg\max_{\mathbf{b}\in\mathcal{B}}\{\mathbf{w}^{T} \mathbf{b}\}\). Then, for all \(\mathbf{a}\in\mathcal{A}\) and \(\mathbf{b}\in\mathcal{B}\), it holds that

\[\mathbf{w}^{T}\mathbf{a}-\frac{\mathbf{w}^{T}\mathbf{a}^{*}+\mathbf{w}^{T} \mathbf{b}^{\dagger}}{2}>0>\mathbf{w}^{T}\mathbf{b}-\frac{\mathbf{w}^{T} \mathbf{a}^{*}+\mathbf{w}^{T}\mathbf{b}^{\dagger}}{2}.\]

Namely, the hyperplane \(\mathbf{w}^{T}\mathbf{x}-\frac{\mathbf{w}^{T}\mathbf{a}^{*}+\mathbf{w}^{T} \mathbf{b}^{\dagger}}{2}=0\) (\(x\in\mathbb{R}^{N}\)) separates the set \(\mathcal{A}\) from the set \(\mathcal{B}\). This completes the proof. \(\blacksquare\)

### Proof of Theorem 7

**Proof of Theorem 7:** (1) The first equality is resulted from the definition of maximum linearly-separable subset. (2) It follows from \(\mathcal{A}_{\circ}\subseteq\mathcal{A}\) and \(\mathcal{B}_{\circ}\subseteq\mathcal{B}\) that

\[\frac{1}{\frac{1}{|\mathcal{A}|}+\frac{1}{|\mathcal{B}|}}\geq\frac{1}{\frac{1}{ |\mathcal{A}_{\circ}|}+\frac{1}{|\mathcal{B}_{\circ}|}}\Longleftrightarrow\frac {|\mathcal{A}_{\circ}|+|\mathcal{B}_{\circ}|}{|\mathcal{A}|+|\mathcal{B}|} \geq\frac{|\mathcal{A}_{\circ}|\cdot|\mathcal{B}_{\circ}|}{|\mathcal{A}|\cdot| \mathcal{B}|}=\mathrm{LS}_{*}(\mathcal{A},\mathcal{B}).\]

The last equality holds because of the definition of \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\). (3) Let \(\boldsymbol{\omega}_{*}\) be the weight vector achieving the MD-LSM \(\mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\). Denote \(\mathcal{A}_{\circ}^{c}=\mathcal{A}\setminus\mathcal{A}_{\circ}\) and \(\mathcal{B}_{\circ}^{c}=\mathcal{B}\setminus\mathcal{B}_{\circ}\). Since \(\mathrm{minor}_{\boldsymbol{\omega}_{*}}(\mathrm{MD}(\mathcal{A},\mathcal{B})) \leq\min\left\{|\mathcal{A}_{\circ}^{c}|\cdot|\mathcal{B}|,|\mathcal{B}_{\circ }^{c}|\cdot|\mathcal{A}|\right\}\), we arrive at

\[1-\frac{\mathrm{minor}_{\boldsymbol{\omega}_{*}}(\mathrm{MD}( \mathcal{A},\mathcal{B}))}{|\mathcal{A}|\cdot|\mathcal{B}|}\geq\max\left\{1- \frac{|\mathcal{A}_{\circ}^{c}|\cdot|\mathcal{B}|}{|\mathcal{A}|\cdot|\mathcal{B} |},1-\frac{|\mathcal{A}|\cdot|\mathcal{B}_{\circ}^{c}|}{|\mathcal{A}|\cdot| \mathcal{B}|}\right\}\] \[\Longleftrightarrow \frac{\mathrm{major}_{\boldsymbol{\omega}_{*}}(\mathrm{MD}( \mathcal{A},\mathcal{B}))}{|\mathcal{A}|\cdot|\mathcal{B}|}\geq\max\left\{ \frac{|\mathcal{A}_{\circ}|\cdot|\mathcal{B}|}{|\mathcal{A}|\cdot|\mathcal{B} |},\frac{|\mathcal{A}|\cdot|\mathcal{B}_{\circ}|}{|\mathcal{A}|\cdot| \mathcal{B}|}\right\}\] \[\Longleftrightarrow \mathrm{LS}_{*}(\mathcal{A},\mathcal{B})\geq\max\left\{\frac{| \mathcal{A}_{\circ}|}{|\mathcal{A}|},\frac{|\mathcal{B}_{\circ}|}{|\mathcal{B}|} \right\}.\]

This completes the proof. \(\blacksquare\)
### Proof of Theorem 9

**Proof of Theorem 9:** Since \(\mathbf{V}^{T}\mathbf{m}_{ij}=\mathbf{V}^{T}(\mathbf{a}_{i}-\mathbf{b}_{j})\), we have

\[\mathrm{LS}_{0}(\mathbf{V}(\mathcal{A}),\mathbf{V}(\mathcal{B})) =\max_{\mathbf{w}\in\mathbb{R}^{\mathbf{H}}}\left\{\max\left\{ \frac{\sum\limits_{i\leq I,j\leq J}\mathrm{sgn}(\mathbf{w}^{T}\mathbf{V}^{T} \mathbf{m}_{ij})}{|\mathrm{MD}(\mathbf{V}(\mathcal{A}),\mathbf{V}(\mathcal{B}) )|},\frac{\sum\limits_{i\leq I,j\leq J}\mathrm{sgn}(-\mathbf{w}^{T}\mathbf{V}^ {T}\mathbf{m}_{ij})}{|\mathrm{MD}(\mathbf{V}(\mathcal{A}),\mathbf{V}(\mathcal{ B}))|}\right\}\right\}\] \[=\max_{\boldsymbol{\omega}\in\mathbb{R}^{N}}\left\{\max\left\{ \frac{\sum\limits_{i\leq I,j\leq J}\mathrm{sgn}(\boldsymbol{\omega}^{T} \mathbf{m}_{ij})}{|\mathrm{MD}(\mathcal{A},\mathcal{B})|},\frac{\sum\limits_{ i\leq I,j\leq J}\mathrm{sgn}(-\boldsymbol{\omega}^{T}\mathbf{m}_{ij})}{| \mathrm{MD}(\mathcal{A},\mathcal{B})|}\right\}\right\}\] \[=\mathrm{LS}_{0}(\mathcal{A},\mathcal{B}).\]

The rest can also be proven in the same way. This completes the proof.

### Proof of Theorem 11

**Proof of Theorem 11:** Denote \(\mathbf{m}_{0}=\mathbf{a}-\mathbf{b}\) and \(\mathbf{n}_{0}=\mathbf{V}_{\sigma}(\mathbf{a})-\mathbf{V}_{\sigma}(\mathbf{b})\). Without the loss of generality, we assume that the point \(\mathbf{m}_{0}\) lies in the major side of the hyperplane \(\boldsymbol{\omega}^{T}\mathbf{m}=0\). Consider the following Taylor's expansion:

\[\mathbf{V}_{\sigma}(\mathbf{a}) =\] \[= \mathbf{V}_{\sigma}(\mathbf{b})+\left(\begin{array}{c}\sigma^{ \prime}(\left\langle\mathbf{v}_{1},\mathbf{b}\right\rangle)\cdot\left\langle \mathbf{v}_{1},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime\prime}(\left \langle\mathbf{c}_{1},\mathbf{v}_{1}\right\rangle)}{2}\cdot\mathbf{v}_{1}^{T} \mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{1}\\ \vdots\\ \sigma^{\prime}(\left\langle\mathbf{v}_{H},\mathbf{b}\right\rangle)\cdot \left\langle\mathbf{v}_{H},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime \prime}(\left\langle\mathbf{c}_{H},\mathbf{v}_{H}\right\rangle)}{2}\cdot \mathbf{v}_{H}^{T}\mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{H}\end{array} \right)\] \[\approx \mathbf{V}_{\sigma}(\mathbf{b})+\left(\begin{array}{c}\sigma^{ \prime}(\left\langle\mathbf{v}_{1},\mathbf{b}\right\rangle)\cdot\left\langle \mathbf{v}_{1},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime\prime}(\left \langle\mathbf{b},\mathbf{v}_{1}\right\rangle)}{2}\cdot\mathbf{v}_{1}^{T} \mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{1}\\ \vdots\\ \sigma^{\prime}(\left\langle\mathbf{v}_{H},\mathbf{b}\right\rangle)\cdot \left\langle\mathbf{v}_{H},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime \prime}(\left\langle\mathbf{b},\mathbf{v}_{H}\right\rangle)}{2}\cdot\mathbf{v} _{H}^{T}\mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{H}\end{array}\right),\]

where \(\boldsymbol{\zeta}_{1},\cdots,\boldsymbol{\zeta}_{H}\) are \(H\) points lying on the line segment between the two points \(\mathbf{a}\) and \(\mathbf{b}\). Alternatively, we also have

\[\mathbf{V}_{\sigma}(\mathbf{b}) \approx \mathbf{V}_{\sigma}(\mathbf{a})+\left(\begin{array}{c}-\sigma^{ \prime}(\left\langle\mathbf{v}_{1},\mathbf{a}\right\rangle)\cdot\left\langle \mathbf{v}_{1},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime\prime}(\left \left\langle\mathbf{a},\mathbf{v}_{1}\right\rangle)}{2}\cdot\mathbf{v}_{1}^{T} \mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{1}\\ \vdots\\ -\sigma^{\prime}(\left\langle\mathbf{v}_{H},\mathbf{a}\right\rangle)\cdot \left\langle\mathbf{v}_{H},\mathbf{m}_{0}\right\rangle+\frac{\sigma^{\prime \prime}(\left\left\langle\mathbf{a},\mathbf{v}_{H}\right\rangle)}{2}\cdot \mathbf{v}_{H}^{T}\mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{H}\end{array} \right).\]
Then, we arrive at

\[\mathbf{n}_{0} = \mathbf{V}_{\sigma}(\mathbf{a})-\mathbf{V}_{\sigma}(\mathbf{b})\] \[\approx \left(\begin{array}{c}\frac{\sigma^{\prime}(\langle\mathbf{v}_{1 },\mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{1},\mathbf{a}\rangle)}{2 }\cdot\langle\mathbf{v}_{1},\mathbf{m}_{0}\rangle+\frac{\sigma^{\prime\prime }(\langle\mathbf{b},\mathbf{v}_{1}\rangle)-\sigma^{\prime\prime}(\langle \mathbf{a},\mathbf{v}_{1}\rangle)}{4}\cdot\mathbf{v}_{1}^{T}\mathbf{m}_{0} \mathbf{m}_{0}^{T}\mathbf{v}_{1}\\ \vdots\\ \frac{\sigma^{\prime}(\langle\mathbf{v}_{H},\mathbf{b}\rangle)+\sigma^{\prime }(\langle\mathbf{v}_{H},\mathbf{a}\rangle)}{2}\cdot\langle\mathbf{v}_{H}, \mathbf{m}_{0}\rangle+\frac{\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v} _{H}\rangle)-\sigma^{\prime\prime}(\langle\mathbf{a},\mathbf{v}_{H}\rangle)}{4 }\cdot\mathbf{v}_{H}^{T}\mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{H}\\ = \left(\begin{array}{c}\frac{\sigma^{\prime}(\langle\mathbf{v}_{1},\mathbf{b }\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{1},\mathbf{a}\rangle)}{2}\cdot \langle\mathbf{v}_{1},\mathbf{m}_{0}\rangle\\ \vdots\\ \frac{\sigma^{\prime}(\langle\mathbf{v}_{H},\mathbf{b}\rangle)+\sigma^{\prime }(\langle\mathbf{v}_{H},\mathbf{a}\rangle)}{2}\cdot\langle\mathbf{v}_{H}, \mathbf{m}_{0}\rangle\end{array}\right)+\left(\begin{array}{c}\frac{\sigma^ {\prime\prime}(\langle\mathbf{b},\mathbf{v}_{1}\rangle)-\sigma^{\prime\prime}( \langle\mathbf{a},\mathbf{v}_{1}\rangle)}{4}\cdot\mathbf{v}_{1}^{T}\mathbf{m} _{0}\mathbf{m}_{0}^{T}\mathbf{v}_{1}\\ \vdots\\ \frac{\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{H}\rangle)-\sigma^{ \prime\prime}(\langle\mathbf{a},\mathbf{v}_{H}\rangle)}{4}\cdot\mathbf{v}_{H}^ {T}\mathbf{m}_{0}\mathbf{m}_{0}^{T}\mathbf{v}_{H}\end{array}\right)\] \[= \widetilde{\mathbf{V}}^{T}\mathbf{m}_{0}+\mathbf{q}(\mathbf{V}, \mathbf{m}_{0})\] \[= \mathbf{p}(\mathbf{V},\mathbf{m}_{0})+\mathbf{q}(\mathbf{V}, \mathbf{m}_{0}).\]

with

\[\widetilde{\mathbf{V}}=\left[\frac{\left[\sigma^{\prime}(\langle\mathbf{v}_{1 },\mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{1},\mathbf{a}\rangle) \right]\mathbf{v}_{1}}{2},\ldots,\frac{\left[\sigma^{\prime}(\langle\mathbf{v }_{H},\mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{H},\mathbf{a} \rangle)\right]\mathbf{v}_{H}}{2}\right].\]

Since the first derivate \(\sigma^{\prime}(\cdot)\) is non-negative, the relative position of the point \(\widetilde{\mathbf{V}}^{T}\mathbf{m}_{0}\) will not be changed, _i.e.,_ the point \(\mathbf{p}(\mathbf{V},\mathbf{m}_{0})\) still lies in the major side of the hyperplane \((\boldsymbol{\omega}^{T}\mathbf{V})\cdot\mathbf{n}_{0}=0\). To change the relative position of \(\mathbf{p}(\mathbf{V},\mathbf{m}_{0})\) w.r.t. the hyperplane \((\boldsymbol{\omega}^{T}\mathbf{V})\mathbf{n}_{0}=0\), the following condition should be satisfied: denoting \(\mathbf{w}^{T}=\boldsymbol{\omega}^{T}\mathbf{V}\),

\[\left\{\begin{array}{c}|\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0}) |<|\mathbf{w}^{T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})|;\\ \mathbf{p}^{T}(\mathbf{V},\mathbf{m}_{0})\cdot\mathbf{q}(\mathbf{V},\mathbf{m }_{0})<0.\end{array}\right.\]

The second formula is equivalent to

\[\mathbf{p}^{T}(\mathbf{V},\mathbf{m}_{0})\cdot\mathbf{q}(\mathbf{V },\mathbf{m}_{0})<0\] \[\Longleftrightarrow \sum_{h=1}^{H}\left[\sigma^{\prime}(\langle\mathbf{v}_{h}, \mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{a}\rangle) \right]\cdot\left[\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h} \rangle)-\sigma^{\prime\prime}(\langle\mathbf{a},\mathbf{v}_{h}\rangle) \right]\cdot\frac{\langle\mathbf{v}_{h},\mathbf{m}_{0}\rangle^{3}}{8}<0\] \[\Longleftrightarrow \Big{[}\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{b}\rangle)+ \sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{a}\rangle)\Big{]}\cdot\Big{[} \sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)-\sigma^{\prime \prime}(\langle\mathbf{a},\mathbf{v}_{h}\rangle)\Big{]}\cdot\langle\mathbf{v}_{h },\mathbf{m}_{0}\rangle<0.\]

Namely, the sufficient condition for the second relation is that the points \(\mathbf{a},\mathbf{b}\) and the weights \(\mathbf{v}_{1},\cdots,\mathbf{v}_{H}\) satisfy that \(F_{1}(\langle\mathbf{a},\mathbf{v}_{h}\rangle,\langle\mathbf{b},\mathbf{v}_{h} \rangle)>0\) holds for any \(1\leq h\leq H\), where

\[F_{1}(x,y)=\left[\sigma^{\prime}(x)+\sigma^{\prime}(y)\right]\cdot\Big{[}\sigma^ {\prime\prime}(x)-\sigma^{\prime\prime}(y)\Big{]}\cdot(x-y),\ \ (x,y)\in\mathbb{R}\times\mathbb{R}.\]

Next, we also need to consider the first relation

\[|\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})|<|\mathbf{w}^{T}\mathbf{q} (\mathbf{V},\mathbf{m}_{0})|.\]

Since the sign of \(\mathbf{m}_{0}^{T}\mathbf{v}_{h}\) is always opposite to that of \(\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)-\sigma^{\prime \prime}(\langle\mathbf{a},\mathbf{v}_{h}\rangle)\), we only need to consider the magnitudes of \(\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})\) and \(-\mathbf{w}^{T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})\).
1. If the sign of \(\langle\mathbf{v}_{h},\mathbf{w}\rangle\) is same as that of \(\langle\mathbf{v}_{h},\mathbf{m}_{0}\rangle\) for any \(h\in\{1,\cdots,H\}\), then we have \[|\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})|<|\mathbf{w}^ {T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})|\] \[\Longleftrightarrow \mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})<-\mathbf{w}^ {T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})\] \[\Longleftrightarrow \sum_{h=1}^{H}\frac{(\mathbf{v}_{h}^{T}\mathbf{w})\big{[}\sigma ^{\prime}(\langle\mathbf{v}_{h},\mathbf{b}\rangle)+\sigma^{\prime}(\langle \mathbf{v}_{h},\mathbf{a}\rangle)\big{]}(\mathbf{v}_{h}^{T}\mathbf{m}_{0})}{2}\] \[<-\sum_{h=1}^{H}\frac{(\mathbf{v}_{h}^{T}\mathbf{w})\big{[}\sigma ^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)-\sigma^{\prime \prime}(\langle\mathbf{a},\mathbf{v}_{h}\rangle)\big{]}(\mathbf{v}_{h}^{T} \mathbf{m}_{0})^{2}}{4},\quad\forall h\in\{1,2,\cdots,H\}\] \[\Longleftrightarrow 2\big{[}\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{b} \rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{a}\rangle)\big{]}< \big{[}\sigma^{\prime\prime}(\langle\mathbf{a},\mathbf{v}_{1}\rangle)-\sigma ^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)\big{]}(\mathbf{v}_{h }^{T}\mathbf{m}_{0}),\quad\forall h\in\{1,2,\cdots,H\}\] \[\Longleftrightarrow 2<\frac{\big{[}\sigma^{\prime\prime}(\langle\mathbf{a}, \mathbf{v}_{h}\rangle)-\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h} \rangle)\big{]}(\mathbf{v}_{h}^{T}\mathbf{m}_{0})}{\big{[}\sigma^{\prime}( \langle\mathbf{v}_{h},\mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h },\mathbf{a}\rangle)\big{]}},\quad\forall h\in\{1,2,\cdots,H\}.\]
2. If the sign of \(\langle\mathbf{v}_{h},\mathbf{w}\rangle\) is the same as that of \(-\langle\mathbf{v}_{h},\mathbf{m}_{0}\rangle\) for any \(h\in\{1,\cdots,H\}\), then we have \[|\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})|<|\mathbf{w}^ {T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})|\] \[\Longleftrightarrow -\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})<\mathbf{w}^ {T}\mathbf{q}(\mathbf{V},\mathbf{m}_{0})\] \[\Longleftrightarrow \sum_{h=1}^{H}\frac{(\mathbf{v}_{h}^{T}\mathbf{w})\big{[}\sigma ^{\prime}(\langle\mathbf{v}_{h},\mathbf{b}\rangle)+\sigma^{\prime}(\langle \mathbf{v}_{h},\mathbf{a}\rangle)\big{]}(\mathbf{v}_{h}^{T}\mathbf{m}_{0})}{2}\] \[>-\sum_{h=1}^{H}\frac{(\mathbf{v}_{h}^{T}\mathbf{w})\big{[}\sigma ^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)-\sigma^{\prime\prime }(\langle\mathbf{a},\mathbf{v}_{h}\rangle)\big{]}(\mathbf{v}_{h}^{T}\mathbf{m }_{0})^{2}}{4}\] \[\Longleftrightarrow 2\big{[}\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{b} \rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{a}\rangle)\big{]}< \big{[}\sigma^{\prime\prime}(\langle\mathbf{a},\mathbf{v}_{1}\rangle)-\sigma ^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)\big{]}(\mathbf{v}_{h }^{T}\mathbf{m}_{0}),\quad\forall h\in\{1,2,\cdots,H\}\] \[\Longleftrightarrow 2<\frac{\big{[}\sigma^{\prime\prime}(\langle\mathbf{a}, \mathbf{v}_{h}\rangle)-\sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h} \rangle)\big{]}(\mathbf{v}_{h}^{T}\mathbf{m}_{0})}{\big{[}\sigma^{\prime}( \langle\mathbf{v}_{h},\mathbf{b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h },\mathbf{a}\rangle)\big{]}},\quad\forall h\in\{1,2,\cdots,H\}.\]

To sum up, the sufficient condition for \(|\mathbf{w}^{T}\mathbf{p}(\mathbf{V},\mathbf{m}_{0})|<|\mathbf{w}^{T}\mathbf{q} (\mathbf{V},\mathbf{m}_{0})|\) is

\[2<\frac{\big{[}\sigma^{\prime\prime}(\langle\mathbf{a},\mathbf{v}_{h}\rangle)- \sigma^{\prime\prime}(\langle\mathbf{b},\mathbf{v}_{h}\rangle)\big{]}(\mathbf{v} _{h}^{T}\mathbf{m}_{0})}{\big{[}\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{ b}\rangle)+\sigma^{\prime}(\langle\mathbf{v}_{h},\mathbf{a}\rangle)\big{]}}, \qquad\forall h\in\{1,2,\cdots,H\}.\]

Denote the function

\[F_{\sigma}(x,y)=\frac{\big{[}\sigma^{\prime\prime}(x)-\sigma^{\prime\prime}(y) \big{]}(x-y)}{\big{[}\sigma^{\prime}(x)+\sigma^{\prime}(y)\big{]}},\ \ (x,y)\in\mathbb{R}\times\mathbb{R}.\]
It is clear that the right hand side of the above formula is \(F_{\sigma}(\langle{\bf a},{\bf v}_{h}\rangle,\langle{\bf b},{\bf v}_{h}\rangle)\). Then, the above issue is equivalent to finding the range such that \(F_{\sigma}(x,y)>2\). Namely, as long as the points \({\bf a},{\bf b}\) and the weight vectors \({\bf v}_{1},\cdots,{\bf v}_{H}\) satisfy that \(F_{\sigma}(\langle{\bf a},{\bf v}_{h}\rangle,\langle{\bf b},{\bf v}_{h} \rangle)>2\) (\(\forall h\in\{1,2,\cdots,H\}\)), the point \({\bf n}_{0}={\bf V}_{\sigma}({\bf a})-{\bf V}_{\sigma}({\bf b})\) lies in the minor side of the hyperplane \({\bf w}^{T}{\bf n}=({\boldsymbol{\omega}}^{T}{\bf V}){\bf n}=0\). Since \(F_{\sigma}(\langle{\bf a},{\bf v}_{h}\rangle,\langle{\bf b},{\bf v}_{h} \rangle)>2\) implies that \(F_{1}(\langle{\bf a},{\bf v}_{h}\rangle,\langle{\bf b},{\bf v}_{h}\rangle)>0\), this completes the proof. \(\blacksquare\)

### Proof of Corollary 13

**Proof of Corollary 13:** For convenience, we briefly denote \(a^{L}:={\rm LS}_{2}({\bf V}_{\sigma}^{L}({\cal A}),{\bf V}_{\sigma}^{L}({ \cal B}))\), \(a^{0}={\rm LS}_{2}({\cal A},{\cal B})\) and \({\bf V}^{(0)}={\bf I}\). According to the law of total probability, we have

\[\mathbb{P}\{a^{L}>a^{0}\} \tag{12}\] \[= \mathbb{P}\{a^{L}>a^{0}|a^{L-1}>a^{0}\}\cdot\mathbb{P}\{a^{L-1}> a^{0}\}+\mathbb{P}\{a^{L}>a^{0}|a^{L-1}\leq a^{0}\}\cdot\mathbb{P}\{a^{L-1} \leq a^{0}\}\] \[\leq \mathbb{P}\{a^{L-1}>a^{0}\}+\mathbb{P}\{a^{L}>a^{0}|a^{L-1}\leq a ^{0}\}\cdot\mathbb{P}\{a^{L-1}\leq a^{0}\}\] \[= \mathbb{P}\{a^{L-1}>a^{0}\}+\mathbb{P}\{a^{L}>a^{0},a^{L-1}\leq a ^{0}\}\] \[\leq \mathbb{P}\{a^{L-1}>a^{0}\}+\mathbb{P}\{a^{L}>a^{L-1}\}\] \[= \mathbb{P}\{a^{L-1}>a^{0}\}+\sum_{{\bf V}^{(1)},\cdots,{\bf V}^{( L-1)}}\mathbb{P}({\bf V}^{(1)},\cdots,{\bf V}^{(L-1)})\cdot\mathbb{P}\{a^{L}>a ^{L-1}|{\bf V}^{(1)},\cdots,{\bf V}^{(L-1)}\}\] \[\leq \mathbb{P}\{a^{L-1}>a^{0}\}+\max_{{\bf V}^{(1)},\cdots,{\bf V}^{ (L-1)}}\mathbb{P}\{a^{L}>a^{L-1}|{\bf V}^{(1)},\cdots,{\bf V}^{(L-1)}\}\] \[\vdots\] \[\leq \sum_{l=1}^{L}\max_{{\bf V}^{(1)},\cdots,{\bf V}^{(l-1)}}\mathbb{ P}\{a^{l}>a^{l-1}|{\bf V}^{(1)},\cdots,{\bf V}^{(l-1)}\}.\]

The combination of Eq. (7) and Eq. (12) leads to the result (8). This completes the proof. \(\blacksquare\)

### Proof of Proposition 16

**Proof of Proposition 16:** Denote \({\bf A}=[{\bf a}_{1},\cdots,{\bf a}_{I}]\) and \({\bf B}=[{\bf b}_{1},\cdots,{\bf b}_{J}]\). Let \({\bf 1}=(1,\cdots,1)^{T}\) be the vector whose components are all ones. Since \({\boldsymbol{\mu}}_{a}=\frac{1}{I}{\bf A}{\bf 1}\) and \([{\boldsymbol{\mu}}_{a},\cdots,{\boldsymbol{\mu}}_{a}]=\frac{1}{I}{\bf A}{\bf 1} {\bf 1}^{T}\), we have

\[{\bf A}_{c}{\bf A}_{c}^{T} = \left({\bf A}-\frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}\right)\left({\bf A}- \frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}\right)^{T}\] \[= {\bf A}{\bf A}^{T}-\frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{\bf A}^{T}- \frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{\bf A}^{T}+\frac{1}{I^{2}}{\bf A}{\bf 1}{ \bf 1}^{T}{\bf 1}^{T}{\bf A}^{T}\] \[= {\bf A}{\bf A}^{T}-\frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{\bf A}^{T}- \frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{\bf A}^{T}+\frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{ \bf A}^{T}\] \[= {\bf A}{\bf A}^{T}-\frac{1}{I}{\bf A}{\bf 1}{\bf 1}^{T}{\bf A}^{T}.\]

In the similar way, we also have \({\bf B}_{c}{\bf B}_{c}^{T}={\bf B}{\bf B}^{T}-\frac{1}{J}{\bf B}{\bf 1}{\bf 1}^{T}{\bf B}^{T}\). Thus, the matrices \({\bf S}_{w}\) and \({\bf S}_{b}\) can be
rewritten as

\[\mathbf{S}_{w} = \mathbf{A}_{c}\mathbf{A}_{c}^{T}+\mathbf{B}_{c}\mathbf{B}_{c}^{T}\] \[= \mathbf{A}\mathbf{A}^{T}+\mathbf{B}\mathbf{B}^{T}-\frac{1}{I} \mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{A}^{T}-\frac{1}{J}\mathbf{B}\mathbf{1 }\mathbf{1}^{T}\mathbf{B}^{T};\] \[\mathbf{S}_{b} = (\boldsymbol{\mu}_{a}-\boldsymbol{\mu}_{b})(\boldsymbol{\mu}_{a}- \boldsymbol{\mu}_{b})^{T}\] \[= \frac{1}{I^{2}}\mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{A}^{T}+ \frac{1}{J^{2}}\mathbf{B}\mathbf{1}\mathbf{1}^{T}\mathbf{B}^{T}-\frac{1}{IJ} \mathbf{A}\mathbf{1}^{T}\mathbf{B}^{T}-\frac{1}{IJ}\mathbf{B}\mathbf{1} \mathbf{1}^{T}\mathbf{A}^{T}.\]

Denote

\[\mathrm{D}(\mathbf{A};J) := \underbrace{[\mathbf{a}_{1},\cdots,\mathbf{a}_{I},\cdots, \mathbf{a}_{1},\cdots,\mathbf{a}_{I}]}_{J\text{ groups of }\{\mathbf{a}_{1},\cdots, \mathbf{a}_{I}\}}\in\mathbb{R}^{N\times IJ};\] \[\mathrm{D}(\mathbf{B};I) := \underbrace{[\mathbf{b}_{1},\cdots,\mathbf{b}_{J},\cdots, \mathbf{b}_{1},\cdots,\mathbf{b}_{J}]}_{I\text{ groups of }\{\mathbf{b}_{1},\cdots, \mathbf{b}_{J}\}}\in\mathbb{R}^{N\times IJ}.\]

Since \(\mathbf{m}_{ij}=\mathbf{a}_{i}-\mathbf{b}_{j}\), \(\mathbf{M}\) can be rewritten as

\[\mathbf{M} = [\mathbf{m}_{11},\cdots,\mathbf{m}_{1J},\cdots,\mathbf{m}_{i1}, \cdots,\mathbf{m}_{iJ},\cdots,\mathbf{m}_{I1},\cdots,\mathbf{m}_{IJ}]_{N\times IJ}\] \[= \mathrm{D}(\mathbf{A};J)-\mathrm{D}(\mathbf{B};I).\]

Then, we have

\[\widetilde{\mathbf{m}}\widetilde{\mathbf{m}}^{T} = \left(\sum_{ij}\mathbf{m}_{ij}\right)\left(\sum_{ij}\mathbf{m}_{ ij}\right)^{T}\] \[= \left[\mathrm{D}(\mathbf{A};J)\mathbf{1}-\mathrm{D}(\mathbf{B}; I)\mathbf{1}\right]\cdot\left[\mathrm{D}(\mathbf{A};J)\mathbf{1}-\mathrm{D}( \mathbf{B};I)\mathbf{1}\right]^{T}\] \[= \mathrm{D}(\mathbf{A};J)\mathbf{1}\mathbf{1}^{T}\mathrm{D}^{T}( \mathbf{A};J)+\mathrm{D}(\mathbf{B};I)\mathbf{1}\mathbf{1}^{T}\mathrm{D}^{T}( \mathbf{B};I)\] \[\qquad\qquad\qquad-\mathrm{D}(\mathbf{B};I)\mathbf{1}\mathbf{1}^ {T}\mathrm{D}^{T}(\mathbf{A};J)-\mathrm{D}(\mathbf{A};J)\mathbf{1}\mathbf{1}^ {T}\mathrm{D}^{T}(\mathbf{B};I)\] \[= J^{2}\mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{A}^{T}+I^{2} \mathbf{B}\mathbf{1}\mathbf{1}^{T}\mathbf{B}^{T}-IJ\mathbf{B}\mathbf{1} \mathbf{1}^{T}\mathbf{A}^{T}-IJ\mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{B}^ {T}\] \[= I^{2}J^{2}\left(\frac{1}{I^{2}}\mathbf{A}\mathbf{1}\mathbf{1}^{T }\mathbf{A}^{T}+\frac{1}{J^{2}}\mathbf{B}\mathbf{1}\mathbf{1}^{T}\mathbf{B}^ {T}-\frac{1}{IJ}\mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{B}^{T}-\frac{1}{IJ} \mathbf{B}\mathbf{1}\mathbf{1}^{T}\mathbf{A}^{T}\right).\]

It is direct that

\[I^{2}J^{2}\mathbf{S}_{b}=\widetilde{\mathbf{m}}\widetilde{\mathbf{m}}^{T},\]

which implies that the eigenvectors of the two matrices \(\mathbf{S}_{b}\) and \(\widetilde{\mathbf{m}}\widetilde{\mathbf{m}}^{T}\) have the same direction.

Moreover, let \(\mathbf{a}\) and \(\mathbf{b}\) stand for the random variables obeying the probability distributions on the sets \(\mathcal{A}\) and \(\mathcal{B}\), respectively. Since \(\mathbf{A}\mathbf{1}=I\cdot\widehat{\mathbb{E}}\mathbf{a}=\sum_{i=1}^{I} \mathbf{a}_{i}\) and \(\mathbf{B}\mathbf{1}=J\cdot\widehat{\mathbb{E}}\mathbf{b}=\sum_{j=1}^{J} \mathbf{b}_{j}\), we have

\[\mathbf{S}_{w} = \mathbf{A}\mathbf{A}^{T}+\mathbf{B}\mathbf{B}^{T}-\frac{1}{I} \mathbf{A}\mathbf{1}\mathbf{1}^{T}\mathbf{A}^{T}-\frac{1}{J}\mathbf{B} \mathbf{1}\mathbf{1}^{T}\mathbf{B}^{T}\] \[= \mathbf{A}\mathbf{A}^{T}+\mathbf{B}\mathbf{B}^{T}-\Big{[}I( \widehat{\mathbb{E}}\mathbf{a})(\widehat{\mathbb{E}}\mathbf{a})^{T}+J( \widehat{\mathbb{E}}\mathbf{b})(\widehat{\mathbb{E}}\mathbf{b})^{T}\Big{]}.\]
Since \(\sum_{i,j}(\mathbf{a}_{i}\mathbf{b}_{j}^{T}+\mathbf{b}_{j}\mathbf{a}_{i}^{T})=IJ \cdot\widehat{\mathbb{E}}\{\mathbf{ab}^{T}+\mathbf{ba}^{T}\}\), we have

\[\mathbf{MM}^{T} = \big{[}\mathrm{D}(\mathbf{A};J)-\mathrm{D}(\mathbf{B};I)\big{]} \big{[}\mathrm{D}(\mathbf{A};J)-\mathrm{D}(\mathbf{B};I)\big{]}^{T}\] \[= J\mathbf{AA}^{T}+I\mathbf{B}\mathbf{B}^{T}-\sum_{i,j}(\mathbf{ a}_{i}\mathbf{b}_{j}^{T}+\mathbf{b}_{j}\mathbf{a}_{i}^{T})\] \[= J\mathbf{AA}^{T}+I\mathbf{B}\mathbf{B}^{T}-IJ\cdot\widehat{ \mathbb{E}}\{\mathbf{ab}^{T}+\mathbf{ba}^{T}\}.\]

This completes the proof. \(\blacksquare\)

## 7 Conclusion

In general, the properties of deep neural networks are studied based on the backward inference from the network performance. Since neural networks have multilayer composite structures, it is technically difficult to analyze the function relation between the network performance and network structure parameters. To the best of our knowledge, it is still challenging to find applicable tools to directly analyze the effect of network structure parameters on the network performance.

In this paper, we first demonstrate that there exists a synchronicity between the linear separability of hidden layers and the training accuracy in the classification tasks. This finding suggests that the linear separability should be an applicable tool to layer-wisely explore the characteristics of deep networks. Then, we propose the MD-LSM LS\({}_{*}\) to measure the linear separability degree of the outputs of each hidden layer. To alleviate the computation cost, we present some alternative versions of MD-LSMs including LS\({}_{0}\), LS\({}_{1}\) and LS\({}_{2}\). The last one has a closed-form solution via eigenvalue decomposition. In the numerical experiment, we simplify the constraint of the optimization problem (4) to achieve an approximation solution \(\boldsymbol{\omega}\) to these MD-LSMs with a low computation cost (_cf._ Remark 15).

We also analyze the relationship between the network structure parameters and the network performance. First, we provide a sufficient condition that a hidden layer can change the relative position relation between an MD point and the splitting hyperplane linear. Based on random matrix theory, we then demonstrate that the increase of network size can enlarge the probability of increasing the linear separability of hidden layers. The experimental results support our theoretical findings, and show that the synchronicity between the linear separability and network performance widely exists in the process of training popular deep networks (such as MLP, CNN, DBN, ResNet, VGGNet, AlexNet, ViT and GoogLeNet) in binary and multi-class classification tasks. In further works, we will use the MD-LSMs to measure the complexity of deep networks and analyze their generalization performance.

## Appendix A Appendix: Related Works

Following the classical statistical learning theory techniques, it is expected to build a proper complexity measure of neural networks, and then to develop the relevant generalization bounds. Neyshabur _et al._[12] proposed a norm-based framework for measuring the capacity of neural networks, and the measure is expressed as an exponential form of the network depth. Golowich _et al._[13] provided the generalization bound based on Rademacher complexity that is bounded by multiplying the weight norm of each layer, and thus such a bound is also of the exponential form of the network depth. Harvey _et al._[14] used the Vapnik-Chervonenkis (VC) dimension as the complexity measure of the networks with piecewise linear activation functions, and then obtain the generalization bound which
can be regarded as a linear function w.r.t. the network depth, the number of parameters and the number of nonlinear units. Bartlett [15] defined the margin-normalized spectral complexity, which is expressed as the product of the spectral norms of all weight matrices, and then provided the generalization bound based on covering number of neural networks. These results illustrates that the generalization performance of neural networks will become low when the network size increases. It accords with the traditional view of statistical learning theory but is still far away from the empirical observation on the applications of deep neural networks.

By combining the spectral norm and the Frobenius norm of the weight matrices, Neyshabur _et al._[47] obtained the PAC-Bayes generalization bound of the networks with ReLU activation functions and then analyzed the stability of the network against the small perturbations on the weights. Under the PAC-Bayes framework, some works proposed the non-vacuous bounds of deep networks and these results were not dependent on the size or the dimension of parameters. Dziugaite _et al._[48] showed a data-dependent bound, derived from the result of [10], for the deep classifiers trained by SGD method, and then optimized the resultant bound to find a posterior distribution starting from the local minima found by the previous SGD process. Zhou _et al._[49] studied the generalization performance of compressed deep neural networks to explain a phenomenon that compressing a deep network only causes a slight performance change. These works usually assume that the prior or the posterior distribution of model parameters obeys Gaussian or sub-Gaussian, but this assumption may not always hold in practice.

The neural tangent kernel (NTK) method, proposed in [11], suggests that the process of training an infinitely wide neural network should be equivalently as a kernel regression process. Based on NTK, Du _et al._[16] proved that the training error of infinitely wide neural networks of any depth will finally converge to zero. Arora _et al._[17] provided a generalization bound for the two-layer ReLU network by bounding the corresponding NTK. However, since these works assume that the network width is infinite, it is still far away from the actual cases. Moreover, under the same assumption, some works also studied the theoretical properties of the over-parameterized neural networks (_e.g.,_ two-layer ReLU networks) during the SGD training process [18, 19, 20]. To sum up, there still remains a big gap between the recent research achievement and the comprehensive explainability of deep neural networks.

## Appendix B Appendix: Complete Experimental Report

In this part, we provide the experimental results of three kinds of MD-LSMs: LS\({}_{0}\), LS\({}_{1}\) and LS\({}_{2}\). In view of the complicated structures of VGGNet, ResNet-20, GoogLeNet-V1 and ViT, we also draw the structure diagrams to denote their hidden layers or main blocks.

### Mlp

First, we layer-wisely examine the linear separability of the MLPs with five hidden layers, denoted as MLP-5, and ten hidden layers, denoted as MLP-10, respectively. The hidden nodes of MLPs are activated by using Sigmoid functions (denoted as Sigmoid) and ReLU functions (denoted as ReLU), respectively. In Figs. 9-12, we illustrate the experimental results of MLPs in the binary classification tasks. In addition, we also consider the linear separability of MLPs in ten-class classification task, where the network has five hidden layers and its hidden nodes are activated by using ReLU (_cf._ Fig. 13).
### CNN, AlexNet and DBN

Moreover, we examine the linear separability of CNNs with two convolution layers and two pooling layers in binary classification task. All hidden nodes of CNNs are activated by using ReLU (_cf_. Fig. 14). Moreover, the linear separability of AlexNet and DBN is also considered in the same task (_cf_. Figs. 15-17). It is noteworthy that we consider two kinds of AlexNets that have different output activation functions: one is Softmax, denoted as AlexNet (Softmax), and the other is Sigmoid, denoted as AlexNet (Sigmoid). We also simplify the process of training AlexNet (Sigmoid), where the tricks of learning rate decay and data augmentation are not used. Since the learning task (binary classification) is much simpler than the task (ImageNet classification) for which AlexNet was originally designed, the simplified training process is enough to provide a good performance. Thus, the curves of AlexNet (Sigmoid) are smoother than those of AlexNet (Softmax), especially for the LS\({}_{2}\).

### VGGNet, GoogLeNet, ResNet and ViT

Here, we consider the linear separability of the deep networks with complicated hidden-layer structures, including VGGNet, GoogLeNet-V1, ResNet-20 and ViT. Since the structures of these networks can be split into some individual blocks, we first examine the linear separability of the outputs of their main blocks, and then illustrate the LSMs of hidden layers of these networks.

In Tab. 1, we show the arrangement of the structure diagrams and the experimental results.

\begin{table}
\begin{tabular}{c|c|c} \hline Deep Networks & Structure Diagram & Main Blocks & Hidden Layers \\ \hline MLP-5 (ReLU) & & Fig. 9 \\ \hline MLP-5 (Sigmoid) & & Fig. 10 \\ \hline MLP-10 (ReLU) & & Fig. 11 \\ \hline MLP-10 (Sigmoid) & & Fig. 12 \\ \hline MLP (Ten-Class) & & Fig. 13 \\ \hline CNN & & Fig. 14 \\ \hline AlexNet (Softmax) & & Fig. 15 \\ \hline AlexNet (Sigmoid) & & Fig. 16 \\ \hline DBN & & Fig. 17 \\ \hline VGGNet & Fig. 19 & Fig. 18 & Fig. 20 \\ \hline GoogLeNet-V1 & Fig. 21 & Fig. 22 & Fig. 23 \\ \hline ResNet-20 & Fig. 24 & Fig. 25 & Fig. 26 \\ \hline ViT & Fig. 27 & Fig. 28 & Fig. 29 \\ \hline \end{tabular}
\end{table}
Table 1: Numerical Experiment Results
Figure 10: MD-LSM and Accuracy Curves of Hidden Layers of MLP-5 (Sigmoid)

Figure 9: MD-LSM and Accuracy Curves of Hidden Layers of MLP-5 (ReLU)
Figure 11: MD-LSM and Accuracy Curves of Hidden Layers of MLP-10 (ReLU)

Figure 12: MD-LSM and Accuracy Curves of Hidden Layers of MLP-10 (Sigmoid)
Figure 14: MD-LSM and Accuracy Curves of CNN’s Hidden Layers

Figure 13: MD-LSM and Accuracy Curves of Hidden Layers of MLP (Ten-Class)
Figure 16: MD-LSM and Accuracy Curves of Hidden Layers of AlexNet (Sigmoid)

Figure 15: MD-LSM and Accuracy Curves of Hidden Layers of AlexNet (Softmax)
Figure 17: MD-LSM and Accuracy Curves of DBN’s Hidden Layers

Figure 18: MD-LSM and Accuracy Curves of VGGNet’s Main Blocks
Figure 19: Structure of VGGNet
Figure 20: MD-LSM and Accuracy Curves of VGGNet’s Hidden Layers
Figure 21: Structure of GoogleNet-V1

Figure 22: Structure of GoogleNet-V1
Figure 22: MD-LSM and Accuracy Curves of GoogleNet’s Main Blocks
Figure 23: MD-LSM and Accuracy Curves of GoogLeNet’s Hidden Layers
Figure 24: Structure of ResNet-20
Figure 25: MD-LSM and Accuracy Curves of ResNet’s Main Blocks
Figure 26: MD-LSM and Accuracy Curves of ResNet’s Hidden Layers
Figure 28: MD-LSM and Accuracy Curves of ViT’s Main Blocks

Figure 27: Structure of ViT
Figure 29: MD-LSM and Accuracy Curves of ViT’s Hidden Layers