MD-LSM: An Efficient Tool for Real-time Monitoring Linear Separability of Hidden-layer Outputs of Deep Networks

Thanks for your valuable comments on this paper. The following have listed the major comments as well as our responses to them:

(1) RE: no supplementary material is provided, limiting reproducibility and independent evaluation of the results.

Ans: Thanks. In the first submission round, we have uploaded the source code of this paper as a supplementary material. Since the revised version contains some new experiments, we have updated the code accordingly. Please check it.

(2) RE: This statistic is drawn from a single dataset, which is furthermore synthetic, so it cannot be taken at all as a general statistic of the proposed method approximation error. The same holds for the subsequent comparison.

Ans: Thanks. In the revised version, we have added new experiments on the UCI datasets (including Diagnostic, Ionosphere, Maintenance, and Marketing) and the text datasets (including Cora and IMDB) to examine the effectiveness of the proposed MD-LSMs and meanwhile to explore the hidden-layer behaviors of deep networks on different types of classification tasks. Please refer to Table 2, Appendix E.1, E.2 and E.4 of the revised version for the new experimental results.

(3) Overall, I am open to reconsideration, if new comparison are added from the computation perspective, mainly showing how this method is either better than probing given the same time budget, or that given equally good results, it takes less time, otherwise it seems that the contribution on the "efficiency" (which is the main difference to probing) cannot be assessed.

Ans: Thanks. Although some state-of-the-art classifiers can achieve lower computational complexity, for example, the desired computational complexity of logistic regression is $O((I+J)\times p)$ that is lower than the complexity $O(I \times J \times p)$ of the approximate manner of calculating MD-LSMs, where p is the data dimension, I and J are the sample sizes of ${\cal A}$ and ${\cal B}$, respectively.

However, it is noteworthy that such a low complexity is achieved under the assumption that ${\cal A}$ and ${\cal B}$ are linearly separable. If there is no priori knowledge on the data distribution, it becomes hard to achieve the desired computational complexity, because it is difficult to find a reasonable training termination condition and appropriate optimization hyperparameters (such as the initial weights and the learning rate). Similar things could happen with other classifiers in the scenario of real-time monitoring hidden-layer behaviors of deep networks during their training process.

In the revised version, we have added the following sentences to highlight this fact:

“\…...Some state-of-the-art classifiers (such as logistic regression or naive Bayes) have the potential to act as feasible “probes” because of their low desired computational complexities. However, if there is no priori knowledge on the data distribution, the efficiency and the performance of these classifiers could be heavily influenced by some unavoidable factors such as the choice of hyperparameters and the setting of termination conditions, and thus their desired complexities are usually hard to be achieved in practice. Consequently, the “probe” method is unsuitable (at least cannot be directly applied) to detecting the mapping behavior of each hidden layer after each training epoch.......”

Moreover, we have also examine the time costs of implement different LSMs on the UCI datasets, and experimental results show that the proposed approximate manner of calculating MD-LSMs has a high efficiency with only a slight precision sacrifice (see Table 2 of the revised version).

To sum up, the computational complexity of approximately calculating MD-LSMs is higher than the desired computational complexities of some classical classifiers such as the logistic regression. However, the computational complexity of MD-LSM is fixed for arbitrary kind of dataset regardless of its priori knowledge on the data distribution. In contrast, the desired computational complexity of these classifiers are achieved under some specific assumptions (e.g., the dataset is linear separable or the data distribution is known). Unfortunately, these requirements cannot be met in the scenario of real-time monitoring hidden-layer behavior of deep networks. The efficiency of implememting these classifiers could be heavily influenced by the choice of hyperparameters and the setting of termination condition. Thus, I think the method proposed in this paper a really "efficient" one for the real-time monitoring of hidden-layer behavior of deep network especially for the future study on large models.

If this reply has answered your question about the "efficiency" of our method, please reconsider the score of this paper.

Thanks for your reply to our response. Regarding your initial feedback, we had prepared a response letter for the point-by-point response to each of your previous comments. However, due to the word limitation, we were unable to present the full responses in the previous round. Please refer to the link [https://iclr4139.notion.site/pbp] for the point-by-point response that had been prepared in the previous round. Next, we come up with your current comments.

[RE W1 and C4]: Thanks. In the current version, we did not consider logistic regression as the Probe is because it is difficult to choose appropriate learning rate and termination condition for implementing gradient method. More specifically, although a big learning rate could decrease the training iteration, it is possible to cause oscillations near the extreme point. On the contrary, a small learning rate is able to maintain the training stability but the number of iteration is high (i.e., the computation cost is high). Thus, the computational complexity O(np) of logistic regression is indeed a desired one in theory, and it is hard to be achieved in practice.

Although there have been some works on the convergency analysis of training logistic regression, it is still challenging to design a fully-automatic learning rate selection method in practice. Refer to [https://iclr4139.notion.site/ref] for these references. Instead, the GRQ of LDA can be directly calculated without any hyperparameter, and thus the comparison among MD-LSM, GQR and GDV is fairer than that between MD-LSM and logistic regression-based probe.

Next, we also conduct the numerical experiments on this issue. Please refer to the link [https://iclr4139.notion.site/exp] for the experimental results. The code on the new experiment is also provided in this webpage. Please check it.

The experimental results show that 1) the computational cost of logistic regression-based probe is much higher than MD-LSMs in the actual task of real-time monitoring hidden-layer behavior; and 2) the process of training logistic regression is not always stable. Moreover, it should also be noted that if we use the classification accuracy of the logistic regression-based probe as the linear separability measure, it could not provide the well-defined form for the further theoretical analysis.

[RE W2 and C5]: This comment will be replied from the following aspects:

• (1) The experiments for Table 7 are conducted on the four UCI dataset; but the experiments for Table 8 are conducted on the CIFAR-10 dataset that is the one used in the experiments of Fig. 2. Due to different datasets, the results in the two tables are certainly different from each other. I am sorry that we forget to highlight the dataset information in Tab. 8, and we will update it in the next version.
• (2 ) I am sorry that I do not get your point in this sentence "Furthermore, the questioned approximation accuracy was between the $LS_i$ and $\hat{LS}_i$, and the first one are. " Could you clarify it for us? and then we will make the clear response.
• (3) According to your suggestion, we have rearranged the content of Table 2, and added the individual columns to show the overhead/saving in time. Please see the link [https://iclr4139.notion.site/table].
• (4) To make the comparison between MD-LSM and logistic regression, we have conducted the new experiments. Please refer to [https://iclr4139.notion.site/exp] for the detailed experimental results and their discussion.

[RE W3]: I am very sorry that you though that we've completely ignored your W3 comment. In the previous rebuttal round, we had been aware of the W3 comment is the most important one of all your comments. Because of the word limitation, we cannot make the point-by-point response to your comment, and thus we had to integrate some similar comments into one response item.

The previous response of Item (3) is just for this comment, and it had taken up most of the word budget. In addtition, we have conducted new experiments on the comparison between MD-LSM and logistic regression as well as the discission on why the MD-LSM is more suitable than logistic regression (see [https://iclr4139.notion.site/exp]).

[RE W5]: I am sorry that due to the word limitation, it is hard for us to explain this issue in details. Actually, in the previous rebuttal round, we have prepared a detailed response to each of your comment. In fact, the question in this comment has been answered in Appendix B of this paper. The detailed reponse to this comment is referred to Item # (5) of the link [https://iclr4139.notion.site/pbp] for the point-by-point response that had been prepared in the previous round.

Dear reviewer,

Thanks for your reply. First, we are pleased that our new experiments have clarified your misundersandings on this paper at the eleventh hour, but it is regrettable that you reject to reconsider the score of this paper. It is unfair for a lot of efforts, made by all of authors, to carefully reply each of your comments. It was also against the intention of the rebuttal phase.

Frist, it should be noted that, in Table 1 of the initial version, we have stated that the efficiency of linear "probe" cannot satisfy the technical requirment of the task of real-time minitoring hidden-layer behavior because this type of method needs the training process. It is a common knowledge that most of classifiers require the training processes that are time-consuming becasue of the selection of hyperparameters and the setting of termination conditions, especially for the state-of-the-art classifiers (e.g. SVM, logistic regression and random forest). Thus, in the initial version, we did not take so many words on this point, due to the page limitation.

In the first rebuttal round, according to your suggestion, we have added an individualy paragraph to highlight this fact (see Line 123 --- 128 of the revised version). The response was submit on November 22. Regretably, you still have doubts on this point, but your new comments appeared on November 28th, which has been beyond the date ("November 27th: Last day that authors may upload a revised PDF.") of the last time we can upload the revision version. We have lost the last chance to improve this paper according to your suggestion. Therefore, we were only able to report our experimental results on your concern (i.e., the comparision between logistic regression and the proposed MD-LSMs) via anonymous notion links.

At the end of this response, we are very grateful for your careful reading and valuable comments. But, we again hope you to reconsider the score of this paper, because we have already clarified your main misunderstandings and questions on this paper.

We are very grateful for your valuable comments. By carefully reading your comments, we find that there are several misunderstandings on some key aspects of this paper as follows:

• [RE: “assumption that linear separability”] Theorem 2.2 provides a sufficient and necessary condition that two sets are linearly separable, rather than builds some results based on the assumption that two sets are linear separable.

• [RE: “non-linear relationships in complex data distributions”] I think there is some misunderstanding on the main purpose of this paper. The reason of why this paper focuses on the linear separability is due to the working mechanism of the output layer of network-based classifiers for real-world binary classification tasks. In general, the output node of a neural network classifier is activated by using the nonlinear sigmoid or the tanh function, which actually corresponding to the question of how to find a separating hyperplane to divide the dataset into two parts. Because of the nonlinear mapping capability, many complicated real-world classification problems have been successfully solved by using the neural networks all of whose nodes are activated by using such a simple activation function. Unfortunately, it is still open to explain why the neural networks perform well for these complicated problems. This paper aims to provide feasible tool for filling this gap.

  In the revised version, we have added new experiments to examine the effectiveness of our methods in different types of real-world classification problems. Please refer to Appendix E of the revised version.

• [RE: “an absolute measure yet shifts towards an approximation of MD-LSM”]: I think there is a misunderstanding on the meanings of the proposed MD-LSMs $LS_0$, $LS_1$ and $LS_*$, and their quadratic version of $LS_2$. As shown in Table 1, the first three are absolute measures. Since it is hard to calculate them, we then introduce $LS_2$ to simplify their calculations. It is mainly used to obtain the approximate solution vector $\widehat{\omega}$ rather than to evaluate the linear separability. Therefore, there is no contradiction between an absolute measure and the relative approach mentioned in your comment.

• [RE: “KL divergence”]: The KL divergence has been widely used to measure the discrepancy between two distributions. To the best of our knowledge, it is still open on how to use the KL divergence to evaluate the linear separability degree of two point sets. The problem setup of tracking distributional shifts over time, mentioned in your comment, is totally different from the scenario of real-time monitoring the linear separability changes of hidden layer outputs during the process of training deep networks.

• [RE: “the computational burden remains substantial”]: As shown in Table 1, there are two way of evaluating the linear separability degree of dataset: one is to build a classifier, called "Probe"; and the other is to calculate a mathematical term, such as the propsoed MD-LSM, GRQ and GDV. The former generally needs a training process.Their efficiency and the performance could be influenced by the choice of hyperparameters and termination condition, especially when there is no priori knowledge on the data distribution. In contrast, the calculation of MD-LSMs does not need a training process. The proposed approximate manner of calculating them has a high efficiency with only a slight precision sacrifice, and thus meets the technical requirements on the real-time monitoring of the behavior of each hidden layer after each training epoch. Please refer to Table 2 in Section 2.4 and Algorithm 1 & 2 in Appendix C for the comparison with the computational costs of different linear separability meausre.**

• [RE: “error could massively increase with increasing layers”]: The caluculation of MD-LSMs is independent of weight update, and thus has nothing to do with the network training process. Although there could be a slight discrepancy between their exact values and the approximate ones, this discrepancy cannot be transferred to other hidden layers. We have examined the effectiveness of the proposed methods for several popular deep networks on the UCI datasets (including Diagnostic, Ionosphere, Maintenance and Marketing) and the text datasets (including Cora and IMDB). I think these empirical evidences are sufficient to support the validity of our results.

• [RE: " synchronicity between training accuracy and MD-LSM"]: The synchronicity exists between the training performance and the linear separability degree of hidden-layer outputs, where the linear separability degree is just measured by using the absolute measures ${\rm LS}_*$, ${\rm LS}_0$ and ${\rm LS}_1$, rather than their quadratic version ${\rm LS}_2$ that is a relative measure.

If these misunderstandings have been clarified, we hope you will reconsider the score of this paper.

We really appreciate your positive comments on this paper. The following are the detailed response to your comments

**(1) [RE: “So, we need more intuition below Definition 2.4”]: ** Thanks. In the revised version, we have added the following sentences to give more intuition on the concepts of major and minor sides as well as the idea on how to obtain the the maximum linearly-separable subset:

"......According to Theorem 2.2, the points $m_{ij}\in minor_{{\omega}}(\mathrm{MD}({\cal A},{\cal B}))$ can be eliminated by removing the relevant points ${\bf a}_i$ from ${\cal A}$ or ${\bf b}_j$ from ${\cal B}$, and the rests turn out to be linearly separable....... "

(2) [RE: “I would suggest discussing the implications /intuition when a linear network of one layer is not used”]: Thanks. The proposed MD-LSM is a tool for objectively evaluating the linear separability degree of two sets, and thus it can be freely and independently used to detect the linear separability of arbitrary two sets. For a network with multiple hidden layers, we have calculated the MD-LSMs (including ${\rm LS}_*$, ${\rm LS}_0$, and ${\rm LS}_1$) of the output sets of each hidden layer, and the resultant MD-LSM values directly reflect the current linear separability degree of each hidden layer with the weights updated after the previous epoch. This is also the main purpose of providing the MD-LSMs tool for real-time monitoring the hidden-layer behavior.

In the original version, because of the page limitation, we only illustrate the MD-LSM results of five hidden-layer networks and ten hidden-layer networks. In fact, the similar experimental phenomena have also appeared in the networks with other numbers of hidden layers. As a supplement, in Table 8 of Appendix E.1, we have added the experiments on the networks, the number of whose hidden layers ranges from $1$ to $5$, to illustrate the characteristics of hidden layers more clearly.

(3) [RE: “the discussion on the synchronicity phenomenon should be indicated somewhere in the front of the paper”]: Thanks. In the revised version, we have moved the relevant content on synchronicity to Section 1.2.

(4) [RE: “The notion of multi-point sets, how is this translated to a data set in a standard ML literature.”]: Thanks. The following replies are based on our understanding of this comment:

"Can the notion of multi-point sets considered in this paper be generalizable to the common scenarios of ML literature?"

If your opinion has been misunderstood, please point it out and we will correct it accordingly. The following is the reply to this comment.

• The answer to this question is "Yes", because all concepts proposed in this paper are built in the Euclidean space, where the datasets of most ML problems belong to. Since this paper mainly concerns with the classification tasks, we only take the multi-point sets as examples. In fact, the findings of this paper are suitable to various kinds of datasets, including real-world data, text data and graph data. In the revised version, we have added the experiments on some real-world classification tasks including the text datasets (including Cora and IMDB) and the UCI datasets (including Diagnostic, Ionosphere, Maintenance, and Marketing). Accordingly, the discussion on these new experimental results is also provided in Table 2 and Appendix E.1, E.2, E.4 of the revised version. In addition, we have also considered the application of MD-LSMs on the graph neural network (GNN) (see Appendix E.4 of the revised version).

(5) [RE: Most ML methods involve a nonlinear function in the middle. How does the measure (relative or absolute) deal with that, what is the notion of separability in these contexts?]: Thanks for the instructive comment. Linear separability measures (LSMs) aim to evaluate the linear separability degree of the two sets, this setting originally is to match with the common activation functions (such as sigmoid and tanh) which actually act as a hyperplane to separate the dataset. For the scenario mentioned in this comment, we can introduce the kernel trick into the definition of the proposed MD-LSM, and the notion of separability in this scenario can be converted into that of the linear separability in the feature space. This is an very interesting research issue, and we have added it into our future work list. In the conclusion section, we have added the following sentence:

"Since the high-dimensional vectors appearing in the expressions of MD-LSMs are of the inner-product form, we will introduce the kernel trick into them and then develop the tools of evaluating the degree of non-linear separability between two sets."

Thanks for your valuable comments. The following are the detailed replies to all the comments you made. If we have clarified your confusion on this paper, please reconsider the score of this paper.

(1) [RE: “High computational cost”]: Thanks. In Table 1 of the original version, we have listed the existing methods for evaluating the linear separability degree of dataset. According to the way they are computed, these methods can be divided into two categories: one is to build a classifier, called "Probe"; and the other is to find mathematical terms calculated by using the data points in the dataset, such as GRQ, GDV, linear divisible angle, and smallest thickness which are listed in the table.

The former generally needs a training process, and thus their efficiency and performance could be influenced by the choices of hyperparameters or the setting of termination condition, especially when there is no priori knowledge on the data distribution. That is reason of why we think the "Probe" method based on the state-of-the-art classifiers could not "efficiently" handle the real-time monitoring of hidden-layer behavior of deep network during its training process.

In contrast, the calculation of the mathematical terms (such as GRQ, GDV, linear divisible angle, and smallest thickness) does not need a training process. However, it is still challenging to develop an feasible linear separability measure that can be efficiently calculated especially when the data size is large. For example, as shown in Algorithm 1 and Algorithm 2 of Appendix C, the computational costs of GDQ and GDV are both higher than the approximate manner of calculating the proposed MD-LSM. We also refer to Table 2 of the revised version for the comparison among the time costs of different LSMs on the UCI datasets.

The proposed MD-LSM is still far from being truly efficient one, but it is the best way we know of so far. Compared with the existing LSMs listed in Table 1, it has been able to meet the current technical requirements on the real-time monitoring of the behavior of each hidden layer after each training epoch.

In the revised version, we have added the following sentences to highlight this facts:

“…...Some state-of-the-art classifiers (such as logistic regression or naive Bayes) have the potential to act as feasible “probes” because of their low desired computational complexities. However, if there is no priori knowledge on the data distribution, the efficiency and the performance of these classifiers could be heavily influenced by some unavoidable factors such as the choice of hyperparameters and the setting of termination conditions, and thus their desired complexities are usually hard to be achieved in practice. Consequently, the “probe” method is unsuitable (at least cannot be directly applied) to detecting the mapping behavior of each hidden layer after each training epoch.......”

(2) [RE: “high variance in results”]: Thanks. I think there are some misunderstanding for the results shown in Table 2:

• The statement "especially LS0's poor performance" is not true. As addressed in Line 227-228, it is true that $major_{\omega_*}({MD}(A,B)) = major_{\omega_0}({MD}(A,B))$, which means that ${\rm LS}_*$ and ${\rm LS}_0$ are exactly equivalent.

• Although there are some difference among the separating lines associated with $LS_*$, $LS_0$, and $LS_1$, it is because that they are derived from different optimization problems.

• It is noteworthy that $LS_2$ is not treated as a linear separability measure in this paper. In fact, $LS_2$ is actually a quadratic version of the proposed MD-LSMs (including $LS_{*}$, $LS_0$, and $LS_1$), and is used to provide a feasible way of approximately solving the optimization problems associated with them.

(3) [RE: “The evaluation of the proposed theory is incomplete”]: Due to device limitation, it is difficult for us to implement the real-time monitoring on large-scale datasets. However, in the revised version, we have added new experiments on the UCI datasets (including Diagnostic, Ionosphere, Maintenance, and Marketing) and the text datasets (including Cora and IMDB) to examine the effectiveness of the proposed MD-LSMs and meanwhile to explore the hidden-layer behaviors of deep networks on different types of classification tasks. Please refer to Table 2, Appendix E.1, E.2 and E.4 of the revised version for the new experimental results

We really appreciate your valuable comments on this paper. The following are the detailed response to your comments.

[RE: “Nevertheless, I would like to see, albeit small, but experiments on data closer to real industry tasks.”]: Thanks. In the revised version, we have added experimental results of MD-LSM on the UCI datasets, text classification and graph classification tasks to examine the effectiveness of the proposed MD-LSM on different types of data.

[RE: “no discussions about the applicability of the proposed measure to other classification problems, for example, texts or graphs, are indicated in the article.”]: In the revised version, we have added the experiments on some real-world classification tasks including the text datasets (including Cora and IMDB) and the UCI datasets (including Diagnostic, Ionosphere, Maintenance, and Marketing). Accordingly, the discussion on these new experimental results is also provided in Table 2 and Appendix E.1, E.2, E.4 of the revised version.

[RE: “How will the proposed measure behave for text classification problems, graph classification problems, and other classification problems?”]: In the revised version, we have added the experiments on some real-world classification tasks including the text datasets (including Cora and IMDB) and the UCI datasets (including Diagnostic, Ionosphere, Maintenance, and Marketing). In addition, we have also considered the application of MD-LSMs on the graph neural network (GNN) (see Appendix E.4 of the revised version).