What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement

Summary

By utilizing theoretical tools from quantum physics, the authors propose that a locally connected neural network can accurately predict data if and only if the data distribution exhibits low quantum entanglement under certain feature partitions. Based on this result, they develop a preprocessing method to enhance the compatibility between data distributions and locally connected neural networks. Experimental evaluations using various datasets and models validate their findings.

Strengths

It investigates what makes a data distribution suitable for machine learning from the theories of tensor network and quantum entanglement, which provides a new perspective and tools from other fields to explore the learning theory.

Weaknesses

The numerical experiments are insufficient, it is only applied to randomly arranged data instead of original data which might be more convincing to support the argument.

Questions

1. In corollary 1(line 223), does it still work under other partitions? and what's the motivation for choosing "canonical partition"? 2. It demonstrates that the locally connected neural network is capable of accurate prediction over distribution if only if it admits low entanglements. In the experiments, it increases the entanglement of data via randomly swapping the feature and provides the comparison between a random permutation of features and proposed methods. Why the proposed method, in the numerics (Table 1, 2), is applied to random arrangement data instead of original data? After we manually randomly arrange the data feature, the data might be meaningless which is expected to get bad performance. Thus, is it appropriate to support the argument? If I miss some thing, please correct me.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Summary

The paper investigates criterion that make data distributions suitable for being accurately fit by neural networks using tools from tensor networks. Specifically, it shows that some locally connected neural networks (with polynomial activations) fit a data distribution accurately if and only if the quantum entanglement of the data tensor is sufficiently low under all canonical partitions of the axes. The argument uses the previously established fact that a certain tensor network (locally connected tensor network) is equivalent to a locally connected neural network. The main theoretical contribution is to show that low quantum entanglement across canonical partitions is a necessary and sufficient condition for an arbitrary tensor $T$ to be approximated by the locally connected tensor network $\mathcal{W}_\mathrm{TN}$. The problem of a locally connected neural network fitting a distribution is then identified with the corresponding data tensor being well-approximated by $\mathcal{W}_\mathrm{TN}$, to establish the main claim. Numerical simulations are performed to show that under random swaps of the features of standard datasets (that are known to be well fit by local neural networks), more swaps results in more entanglement and this corresponds to the predictive performance being correspondingly lower. The authors also suggest a heuristic method for improving the compatibility of data to a local neural network architecture, by searching for permutations of the axes that result in a low entanglement.

Strengths

The main result is compelling, providing a clean and computationally efficient measure that may be used to quantify the suitability of a data distribution to certain local neural network architectures. Despite the minor limitations (such as polynomial activations) placed on the corresponding network, this still seems to be significant progress on an important and difficult question. The potential of systematically searching for feature permutations to improve the predictive power of locally connected networks is also an intriguing possibility. The theoretical results seem sound and correct to the best of my knowledge, although I did not check every detail. The numerical results do provide evidence of an increase in predictive power from searching for low entanglement feature permutations.

Weaknesses

1. The presentation of the paper is rather dense in some places, which is understandable due to the breadth of material covered, but makes the exposition hard to follow in places. It would be helpful to have some intuition about how the notions defined in the paper correspond to standard ones in deep learning. For example, the definition of canonical partitions seems unmotivated at first and it may be helpful to the reader if the connection to locality is highlighted. As a minor comment, there are a few terms that are defined once and then used in later statements without context: for example, it would be helpful to mention in Definition 2 that $N = 2^L$, and to have a reminder about $R$ near Corollary 1. 2. Section 5.2.2 only presents numerical results for the proposed preprocessing pipeline against a baseline of randomly permuted features. It is not clear to me whether these improvements manifest for real data ie. data already suited to a locally connected network, with the goal being to improve predictive accuracy. It is unlikely in practice that a preprocessing step would be used to improve the performance of a model with very low predictive accuracy.

Questions

Does the suggested pipeline lead to any accuracy improvements for natural datasets (without randomly permuted features) and local networks that already achieve good performance on them?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Yes

Summary

This paper focuses on the problem that which data distribution is more learnable by locally-connected neural networks such as CNN, RNN, and local-attention. The paper introduces the notation of quantum entanglement, theoretically proves and empirically verifies that the network can achieve accurate predictions if and only if the data distribution exhibits low quantum entanglement under canonical partitions of features.

Strengths

1. This paper introduces the notation of quantum entanglement from physics, which provides new insights into the problem of which data distribution is more learnable by a specific family of neural networks. 2. The paper provides a comprehensive theoretical analysis of the above problem. 3. Overall speaking, the paper is easy to read and follow.

Weaknesses

1. The notion of entanglement is not very intuitive. Although the authors formally introduce the mathematical definition of quantum entanglement, it is still not clear what characteristics a data distribution would exhibit if the distribution has low entanglement. I suggest the authors illustrate this low-entanglement property on toy datasets and/or textual data. This intuitive illustration might provide valuable insights to the machine learning community. 2. The authors are encouraged to conduct comprehensive experiments on more architectures and datasets. For example, for image classification, it is suggested to test on classical CNN architectures such as AlexNet, VGG, and ResNet. Besides, textual data should also be investigated.

Questions

1. In Theorem 1, the authors derive an upper bound for quantum entanglement. However, it is not clear whether this upper bound truly ensures *low* entanglement. There are mainly two terms in the bound, $\ln(R)$ and $\ln(D_\mathcal{K})$. The magnitude of the first term is already addressed by the authors, but it is not clear whether the second term can be extremely large. The authors are encouraged to have a discussion on this issue and show that this upper bound is indeed much smaller than the entanglement of a random tensor (as a baseline). 2. How will the network architecture affect the main theoretical results in Section 3.1, 4.1, and 4.2? For example, I wonder if the results still hold if the neural network has skip connections and batch normalization operations. 3. What does feature (re)arrangement mean in Section 5.1? Let us take textual data as an example and consider a sentence with N words. Does a feature rearrangement mean that the words (as well as their embeddings) in the sentence are randomly permuted? The authors are suggested to make this clearer, and better with examples.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper investigates the representation power of locally connected neural networks, a prevalent family of deep learning architectures, using tools from quantum physics. In particular, following the established equivalence between locally connected neural network and locally connected tensor network, the authors showed that the necessary and sufficient condition of a locally connected neural network fitting an objective tensor is the entanglements of the tensor admits under canonical partitions being small enough. As an application, the authors discuss the condition of making accurate predictions using locally connected neural networks, accompanied by empirical demonstrations. Notably, the findings suggest that the representation power of locally connected neural networks can potentially be enhanced by reorganizing the features to achieve reduced entanglements under canonical partitions.

Strengths

The authors successfully extend the connection between deep learning and quantum physics by revealing a compelling link between representation power and entanglement – two fundamental concepts in both domains. From my perspective, the results are not only theoretically elegant but also closely related to illustrations of practical situations.

Weaknesses

The paper's presentation could benefit from further improvement, especially in providing more qualitative discussions to enhance readers' intuition regarding the technical correspondence between representation power and entanglement. While the link between these two concepts is established, the paper lacks sufficient qualitative explanations to make the connection more accessible. Furthermore, the tensor network's width, denoted as $R$ in the paper, seems to be crucial in the derived bounds. However, the definition of this parameter remains somewhat unclear, so I'm not fully convinced on why it is usually small. Furthermore, the current results solely focus on the representation of tensors using locally connected neural networks. It would be good to include an explanation as to why other types of underlying functions for representation were not considered. If these questions are addressed, I'm happy to further increase my evaluation.

Questions

I don't have more questions other than the existing ones above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

The fundamental question of what makes a data distribution suitable for deep learning is addressed in this study, focusing on locally connected neural networks. The study uses theoretical tools from quantum physics to tackle this problem. The main theoretical finding is that a specific type of locally connected neural network can accurately predict over a data distribution if, and only if, the data distribution shows low quantum entanglement under specific feature partitions. The study suggests that using quantum entanglement could inspire further use of physics tools to understand the relationship between deep learning and real-world data.

Strengths

- The paper technically sounds correct and claims well supported by theoretical analysis and experimental results. - Related works and background knowledge are covered and discussed. - Experiments are conducted extensively in different locally connected neural networks (CNN, RNN, local self-attention), and experimental results are thoroughly discussed.

Weaknesses

- Need more discussion on the motivation of using quantum entanglement. - Need more discussion on the limitations of this study.

Questions

- The whole study targtes at locally connected neural networks. What happens to a NN with high connectivity? Does entanglement help the learning task? - Entanglement entropy is a typical metric. But what does entanglement mean in the dataset? If it is used to quantify the temporal/spatial non-locality in the data, why not use other metrics such as autocorrelation or other metrics from information theory? Why choose entanglement specifically? - Why use a tensor network as the equivalent model instead of directly evaluating on locally connected neural networks? - Will the code be available to reproduce the findings?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Not found.