Understanding the learning process of artificial neural networks requires clarifying the structure of the parameter space within which learning takes place. A neural network parameter's functional equivalence class is the set of parameters implementing the same input--output function. For many architectures, almost all parameters have a simple and well-documented functional equivalence class. However, there is also a vanishing minority of reducible parameters, with richer functional equivalence classes caused by redundancies among the network's units. In this paper, we give an algorithmic characterisation of unit redundancies and reducible functional equivalence classes for a single-hidden-layer hyperbolic tangent architecture. We show that such functional equivalence classes are piecewise-linear path-connected sets, and that for parameters with a majority of redundant units, the sets have a diameter of at most 7 linear segments.
Paper
Similar papers
Peer review
Summary
The paper investigates the functional equivalence class for reducible neural network parameters and its connectivity properties. The authors focus on single-hidden-layer hyperbolic tangent networks, but the findings can be generalized to other feed-forward network components.
Strengths
The paper provides a comprehensive understanding of the functional equivalence class for reducible neural network parameters. This can be key to understanding the structure of the parameter space and the loss landscape on which deep learning takes place. The authors describe a complex union of manifolds, displaying rich qualitative structure. This includes a central discrete array of reduced-form parameters, connected by a network of piecewise linear paths, and various manifolds branching away from this central network. The paper establishes that with a majority of blank units, the diameter of this parameter network becomes a small constant number of linear segments. This can be beneficial in understanding the trade-offs between shortest path length and rank for different unit permutations. The paper also discusses the relevance of their findings to modern architectures and deep learning, suggesting that understanding reducible functional equivalence classes may be key to understanding these topics.
Weaknesses
The paper is highly theoretical and may not provide immediate practical applications for those working with neural networks. The exact relevance of reducible parameters to these topics remains to be clarified. The paper focuses on single-hidden-layer hyperbolic tangent networks, which may limit the applicability of the findings to more complex architectures.
Questions
In the paper, the authors focus on single-hidden-layer hyperbolic tangent networks. How do the authors think the results would change ifwe considered networks with multiple hidden layers or different activation functions? The paper discusses the trade-offs between shortest path length and rank for different unit permutations. Could the authors provide more insights into how these trade-offs could impact the performance of neural networks in practical applications?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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
3 good
Limitations
NA
Summary
The paper introduces an algorithm to calculate the canonical equivalent parameter for a tanh feed-forward network. Further, the full equivalent class of each parameter is given by a union of subsets constructed out of (inverse-)reductions and permutations of the canonical parameter. Finally, the paper shows that each functional equivalence class is path-connected and that the diameter of a functional class with rank at most the half of the number of units in the hidden layer is 7.
Strengths
The canonicalisation algorithm is novel for feed-forward networks with a tanh transfer function. Furthermore, this is the first result that characterizes the diameter of some of the equivalence classes of these networks. The paper fully proves each theorem and includes useful visualizations for the path structure of a functional equivalence class. The paper is overall very clearly written, with only a few possible minor typos. The results presented here could be of importance to loss minimization problems.
Weaknesses
The scope of applications of the algorithm and the theorems seems to be rather narrow or at least is not properly motivated to be broad. The paper has very limited evaluation of the proposed algorithm and further uses of the results. It is for example unclear in which practical application Algorithm 4.1 could be used, because of the real valued parameters being usually all different in a trained network, see Questions.
Questions
196: What is a branch? 265: Should it be ``connect $w'$ to $u$"? What are the practical applications of this algorithm? Could you apply it to a loss function example you mention in 354? If the parameters are real values, wouldn't they (and their absolute values) all be different from each other with probability equal to 1? Could you say anything about the loss function at different parts of the functional class that belongs to zero loss? Is it steeper at certain points in parameter space than others? Could you clarify and justify the remark in 362? What is this approximation? Could you give an example of a network that has rank higher than half of $h$ that is part of a functional equivalence class with a diameter more than 7? Why does it matter what the diameter is of a functional equivalence class? Why are networks that are in a functional equivalence class of diameter at most 7 of particular importance?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
They are adequately discussed.
Summary
This paper focuses on the study of functional equivalence classes in neural networks, specifically in fully-connected, single-layer networks with hyperbolic tangent activation. It presents a Canonicalisation algorithm for reducible networks to determine canonical representative parameters for different functional equivalence classes. Finally, it explores the concept of connectivity between these classes.
Strengths
The paper gives a well-motivation exploration of functional equivalence classes in neural networks. It provides a well-written definition of these classes, introducing an analysis of connectivity between them. The article references foundational works on simple neural networks and incorporates recent literature in the field of deep learning, enhancing the credibility and relevance of the study.
Weaknesses
The weaknesses of this article stem from the focus on a very theoretical network type with implausible parameters. While a useful theoretical case, further discussion on the applicability of this analysis to modern architectures would benefit the article. Specifically, a drawback of the article is its narrow focus on a specific architecture type, namely single-layer networks with tanh activation, a single input and single output. While it does discuss expanding the input and output space, it fails to address how the findings extend to more complex multi-layer networks or different activation functions commonly used in modern architectures. By limiting the scope of investigation, the article has limited application to contemporary neural network design and learning. The proposal of the Canonicalisation algorithm also presents limitations. The algorithm relies on exact equivalence between weights or to 0, which is rarely achievable in practice, especially for weights trained through backpropagation. This raises questions about the adaptability of the Canonicalisation algorithm to networks trained through backpropagation, and whether it can provide meaningful results. The article would greatly benefit from addressing these concerns and exploring potential adaptations for networks trained through backpropagation. It appears to me that the Canonicalisation algorithm is a unit pruning / neuron removal algorithm. While Kuditipudi et al. is cited, the article would benefit from considering and discussing other neuron removal methods, specifically the following which focus on individual neurons in fully-connected layers: + Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In Proceedings of the 37th International Conference on Machine Learning, pp. 10820–10830. PMLR, 2020. + Xiaocong Du, Zheng Li, Yufei Ma, and Yu Cao. Efficient network construction through structural plasticity. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 9(3):453–464, 2019. + Lemeng Wu, Bo Liu, Peter Stone, and Qiang Liu. Firefly Neural Architecture Descent: a General Approach for Growing Neural Networks. In Advances in Neural Information Processing Systems, volume 33, 2020. Additionally, GradMax is a method which adds new neurons, similarly to Fukumizu and Amari, which was cited. The new neurons do not impact the function of the network upon addition by setting fan-in weights to 0. This case doesn't seem covered by remarks 5.3-5.5. Evci, Utku, et al. "GradMax: Growing Neural Networks using Gradient Information." International Conference on Learning Representations. 2021.
Questions
The practical contribution of the path connectivity analysis was furthermore unclear for me. What does this analysis mean for learning or architecture design? Is it an argument for sparse training or initialization to reach an architecture with a majority of blank units? I believe the reference format is incorrect; I believe that NeurIPS uses number-based references instead of name, year.
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
3 good
Presentation
3 good
Contribution
3 good
Limitations
The paper does not adequately address the limitations induced by the narrow focus on a highly theoretical architecture. The sections on "towards modern architectures" and "functional equivalence and deep learning" offer insight into the potential application of the analysis to contemporary deep neural networks, but are not comprehensive.
Summary
This paper deals with functional equivalence problems in neural networks, i.e., the characterization of all neural networks that lead to the same given output function. This is a problem that has been studied since the early 1990s, including work by the fields medalist Charles Fefferman. The present paper considers single-layer networks with tanh-nonlinearity and puts forward a completely new perspective by paying attention to reducible parameters.
Strengths
The paper tackles a problem that has been studied in various guises for over 3 decades, and puts forward a completely new vantage point, by considering reducible parameters. This leads to rich insights into the functional equivalence problem. In addition, the paper exhibits a strong algorithmic component, specifically by providing an algorithmic characterization of redundancies and connecting the underlying theory to the beautiful concept of piecewise-linear path connected sets.
Weaknesses
could not find any
Questions
it would be interesting to see the authors' thoughts on whether the algorithmic component of the paper can be extended to multi-layer networks
Rating
10: Award quality: Technically flawless paper with groundbreaking impact, with exceptionally strong evaluation, reproducibility, and resources, and no unaddressed ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
none
Summary
The paper addresses fully connected feed-forward neural networks (NNs) with a single hidden layer and the hyperbolic tangent activation function. A parameter is thus a vector of weights and biases. It considers reducible parameters, which means that a NN with strictly less neurons can implement the same function. The paper provides a "canonicalise" procedure taking a parameter as input and yielding a canonical parameter that implements the same function. Also, if two parameters implement the same function then the output of the procedure is the same for them. Based on this procedure, the paper characterizes the set of parameters that implement the same function as a given parameter. It shows that this set is piecewise linear path-connected, and if the set is defined with respect to a ``sparse'' parameter, then the number of linear pieces of the diameter of the set is bounded by 7.
Strengths
The paper is well written. The figures are very clear and help understanding. The theoretical topic is well motivated and well connected to the literature. The theoretical results are interesting, and so are the proofs in my opinion.
Weaknesses
The main weakness is that the paper is restricted to a single hidden layer. Also, the hyperbolic tangent activation function is studied, while ReLU would have been more relevant, in my opinion. For these two weaknesses, it seems they cannot really be fixed in the frame of this paper, as considering multiple hidden layers and/or ReLU would probably change the nature of the results and the proofs.
Questions
The content presented is overall clear. The statements of the theoretical results seem clear. Some proofs are a bit technical and more difficult to follow. The authors could consider adding pedagogical content/details on the proofs in the appendix, if they see fit.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
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
3 good
Limitations
The authors adequately discuss the main limitation (a single hidden layer) in the discussion. I do not see potential negative societal impact.
Thanks for the author's response.
Thank you for your extensive response. After discussion with other reviewers, there are a few points I'd like to discuss. Apologies that this response comes so close to the end of the discussion period. In the overall response, you note the lack of "direct evidence of reducible parameters being encountered or approached during training in practical settings, which would be the basis for their relevance to modern deep learning theory." In my view, this appears similar to the question about exactness in the canonicalisation algorithm. Are there reducible parameters in deep learning, given the use of backpropagation and stochastic gradient descent? Are there more if the definition is expanded to include approximate equivalence? The expansive pruning literature would seem to indicate that there are: parameter-based removal and merging work when using approximate equivalence. The relation between parameters which can be removed without changing the function of the network and *reducible* parameters as used in this article appears worthy of exploration. One important distinction is that this article considers reducibility based only on the network parameters, and not on any distribution of data. The insight from architecture search, pruning, and other neural structure literature is that the information from the data distribution can often be useful, as a neural network is used as a function of a certain distribution. That being said, data-free initialization and pruning methods exist, based on functional analysis of the network parameters: Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. 2019. SNIP: Single-shot Network Pruning based on Connection Sensitivity. In International Conference on Learning Representations (ICLR). arXiv:cs.CV/1810.02340 Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. 2020. A Signal Propagation Perspective for Pruning Neural Networks at Initialization. In International Conference on Learning Representations (ICLR). arXiv:cs.LG/1906.06307 Soufiane Hayou, Jean-Francois Ton, Arnaud Doucet, and Yee Whye Teh. 2021. Robust Pruning at Initialization. In International Conference on Learning Representations (ICLR). arXiv:stat.ML/2002.08797 The closest works that I'm familiar with to the canonicalization method are the following, which use data-free analysis of network parameters to merge *similar* parameters: Suraj Srinivas and R. Venkatesh Babu. 2015. Data-free parameter pruning for Deep Neural Networks. In British Machine Vision Conference (BMVC). arXiv:cs.CV/1507.06149 Ben Mussay, Daniel Feldman, Samson Zhou, Vladimir Braverman, and Margarita Osadchy. 2020. Data-Independent Structured Pruning of Neural Networks via Coresets. In International Conference on Learning Representations (ICLR). arXiv:cs.LG/2008.08316 The coreset article is particularly close to the proposed canonicalisation, as it removes entire neurons and not only individual weights. The analysis used for coreset identification in this work may be useful here: instead of considering a single distribution, the functional equivalence of the network is analyzed over an arbitrary vector. A full review of pruning and sparse architectures is given here: Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., & Peste, A. (2021). Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. The Journal of Machine Learning Research, 22(1), 10882-11005. Given this extensive literature and its relevance to the canonical architectures studied in this work, I would appreciate a deeper contextualization of the proposed analysis. The theoretical framework proposed here could be directly linked to these approaches, which have been applied to contemporary deep architectures, thus bringing this work closer to understanding such architectures. Finally, the clarification about the path connectivity analysis is appreciated. In a similar way to my above comments, this approach of studying the learning from canonical architectures appears to me related to the lottery ticket hypothesis: Jonathan Frankle and Michael Carbin. 2019. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In International Conference on Learning Representations (ICLR). arXiv:cs.LG/1803.03635 Do the authors believe that canonical networks are lottery tickets? Could understanding their path connectivity shed light on training sparsely initialized networks?
Response to Reviewer HCLr
**Thank you.** First, thank you so much for these valuable additional literature recommendations. As noted, we are highly interested in exploring the relation between our functional equivalence perspective and the perspective from the literature on pruning and sparsity in deep learning. We appreciate the time you have taken to cite these papers for us. **On the relevance of reducible parameters.** We concur about the potential relation between approximate pruning and approximate reducibility, and the value of future exploration of this direction. In the overall response where we mentioned a 'lack of *direct* evidence' for reducible parameters arising or being approached in learning, we indeed had in mind a number of *indirect* sources of evidence for this hypothesis, including: 1. the literature on pruning (as you point out) broadly suggesting that learned neural networks are often prunable without dramatic changes in their functionality; 2. the broader phenomenon of neural network compressibility (beyond pruning), for example the possibility of model distillation through teacher--student learning; 3. the common use of dropout to enforce redundant functionality within learned networks; and 4. the lottery ticket phenomenon (see also below). **On data-sensitive pruning:** We appreciate the reviewer pointing out this distinction. What we can say on the matter is that, clearly, in practice we care about a restricted form of functional equivalence that is only sensitive to changes in functionality for realistic inputs. This seems similar to the data-dependent pruning approaches you mentioned. Of course, functional equivalence for all inputs is a sufficient (not necessary) condition for such data-sensitive functional equivalence. This is the case we study, which we agree seems related to data-independent pruning approaches, particularly those based on coresets. **On lottery tickets:** As discussed, the existence of sparse subnetworks containing (most of) a model's functionality appears related to reducibility and canonicalisation. In particular, it seems to us that the existence of a lottery ticket implies that a network is (approximately) reducible. We haven't thought about this particular connection before, but it seems that lottery ticket could potentially be related to canonical parameters, but the connection is not immediate. * Roughly, the correspondence would say that the canonical parameter existed as a sparse subnetwork at initialisation. During training, the remaining units would be brought to cancel out so that the behaviour of the sparse subnetwork / canonical parameter could determine the overall function's behaviour. Possibly, the canonical parameter could also distribute its computation by 'splitting' (un-merging) its units into nearby blank units, possibly along paths like those constructed in our paper (e.g. the reverse of the reduction paths). * To the extent that canonicalisation involves eliminating units that do not contribute, or collections of units that can be merged together and then fail to contribute (because they 'cancel each other'), it seems that the units that are left may look like a sparse subnetwork that performs well before and after training. But another important part of canonicalisation is merging units that each contribute meaningfully to the function. If two such units jointly contribute to the function, it would appear that removing either of them from a subnetwork would meaningfully alter the function. This suggests that finding the hypothetical canonical parameter = lottery ticket after training could be difficult if using pruning methods that do not consider merging proportional units. **Overall comments:** > The relation between parameters which can be removed without changing the function of the network and reducible parameters as used in this article appears worthy of exploration. > Given this extensive literature and its relevance to the canonical architectures studied in this work, I would appreciate a deeper contextualization of the proposed analysis. The theoretical framework proposed here could be directly linked to these approaches, which have been applied to contemporary deep architectures, thus bringing this work closer to understanding such architectures. Our above comments are essentially all we have to say so far. If accepted, we would be willing to expand upon the high-level discussion of these related literature(s) in the paper, to better acknowledge this related literature and to call for future work systematically exploring these connections. Unfortunately we are not in a position to promise any detailed exploration of these connections with this submission. We thank reviewer HCLr once again for their detailed review, discussion, and literature recommendations, and for their consideration of our submission. (Note: unfortunately, we are unavailable for further discussion between now and the end of the discussion period in a few hours.)
Thank you for the interesting discussion, and apologies again that I replied close to the deadline. I have modified the score of my original review. If the article is expanded to integrate this discussion and to relate the proposed analysis to pruning, sparse networks, and lottery tickets, I think it could be a valuable theoretical basis for further work in deep learning.
Decision
Accept (poster)