Source-linked AI summary
Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks
Kathlén Kohn, Giovanni Luca Marchetti, Alex Massarenti, Massimiliano Mella
TL;DR
The paper asks how to determine parameter symmetries in polynomial multilayer perceptrons with generic high-degree activations. It connects this problem to linear independence of polynomial compositions, proves the conjecture in several cases, and uses those results to fully resolve identifiability for shallow networks and selected deep architectures.
Problem
For MLPs with generic polynomial activations of large degree, existing results establish only finitely many parameter choices, without determining precise generic conditions or the exact finite fibers.
Method
The paper formulates polynomial-composition linear independence and studies its general and origin-passing variants, proving cases for two polynomials and bounded polynomial degrees.
Results
The established cases resolve identifiability for shallow MLPs and deep MLPs whose activation degrees grow from layer to layer, while explicit activation families work uniformly without growing-degree assumptions.
Takeaways & Limitations
The results connect neural-network identifiability to a commutative-algebra problem that generalizes Newman–Slater’s theorem from monomials to generic polynomials.
Takeaways & Limitations
The identifiability results for MLPs with bias vectors would require a stronger conjecture asserting independence of 1, σ(p1), …, σ(pk).
Abstract
from arXiv · showhide
Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.
1 Introduction
The paper studies identifiability in polynomial multilayer perceptrons through a conjectured linear-independence property of polynomial compositions, extending Newman–Slater’s theorem beyond monomial activations. It proves several cases and applies them to characterize identifiability for important MLP architectures.
- Identifiability asks which parameter choices produce the same function, a foundational question for multilayer perceptrons and other parametrized models.
- For generic polynomial activations of large degree, the paper seeks precise conditions and exact parameter fibers beyond the known finiteness result.
- The central conjecture states that sufficiently high-degree generic polynomial activations map any fixed number of pairwise distinct nonconstant polynomials to linearly independent compositions.
- Its origin-passing variant restricts the activation and input polynomials to vanish at zero and is the form needed for polynomial MLP identifiability.
- The paper proves the conjecture for two polynomials and for arbitrary numbers with bounded degrees, resolving identifiability for shallow MLPs and deep MLPs with increasing activation degrees.
- Explicit activation families also yield uniform linear independence for all pairwise distinct inputs, without growing-degree assumptions in the corresponding deep MLPs.
2 Linear independence of polynomial compositions
The paper studies when generic polynomial composition makes distinct nonconstant polynomials linearly independent, reducing the multivariate problem to one variable and proving several restricted cases.
- Reduction to one variable: Multivariate composition relations can be reduced to univariate polynomials by composing with a general linear map, while preserving degrees, distinctness, and origin-passing.
- Two polynomials: For two distinct nonconstant polynomials, R(2) = 3, and activations satisfying ar∆2(σ)∆3(σ) ≠ 0 guarantee linear independence after composition.The proof compares leading coefficients and successive coefficients after translating the activation.
- Bounded-degree cases: For fixed numbers and maximum degrees, a general sufficiently high-degree activation separates every tuple of distinct polynomials of equal or bounded degree.The argument constructs an incidence variety whose projection is a proper closed bad locus, leaving a nonempty Zariski open good set.
- Conjectural scope: The weak conjecture allows the degree threshold to depend on both the number and maximum degree of the polynomials, and its origin-passing form suffices for polynomial MLP identifiability.
- Explicit activations: Explicit activations provide uniform linear independence for all distinct nonconstant polynomials, showing that openness—not existence—is the central unresolved difficulty.Taking σℓ,f(z) = f(z)^ℓ with ℓ > k(k −2) invokes Newman–Slater; two explicit cubic-based choices are given, one origin-passing.
3 Origin-Passing Polynomials
The origin-passing conjectures seek generic origin-passing activations whose compositions with distinct origin-passing polynomials are linearly independent. The paper proves the two-polynomial case and bounded-degree versions, and gives explicit good activations.
- Conjectures: Origin-passing polynomials satisfy p(0)=0, and the origin-passing conjecture requires generic σ with σ(0)=0.
- Conjectures: The weak origin-passing conjecture allows the open subset of activations to depend on the maximum input-polynomial degree m.
- Two polynomials: For r≥2 and σ(z)=a1z+⋯+arz^r with ar,ar−1≠0, compositions of any two distinct nonzero origin-passing polynomials are non-proportional.
- Bounded degree: When the number k and maximum degree m are fixed, sufficiently large r yields a nonempty Zariski open set of origin-passing activations producing linearly independent compositions.
- Bounded degree: The proofs use incidence varieties and dimension bounds to show that activations causing a nontrivial linear relation form a proper subset.
- Examples: Explicit families, including f(z)^ℓ and (z+1)^r−1, satisfy the origin-passing independence property at stated degree thresholds.
4 Identifiability of Polynomial MLPs
For generic sufficiently high-degree polynomial activations, MLP weights are identifiable precisely up to neuron permutations when no inactive or redundant neurons occur. The proof proceeds inductively by using linear independence of composed neuron polynomials, with established cases covering several architectures and activations.
- An MLP is a composition of layer weight maps and entrywise activation functions across a fixed architecture.
- A subnetwork contains an inactive neuron with vanishing incoming or outgoing weights, or a redundant neuron with duplicated incoming weights.Such neurons can be removed to obtain a smaller MLP representing the same function.
- For activation polynomials in a nonempty Zariski open set with degree r ≥ R(2D), weights are identifiable if and only if they are not a subnetwork.Here D is the maximum hidden-layer width.
- The inductive proof shows that penultimate-layer neuron outputs are nonzero and pairwise distinct, then applies composition linear independence to recover the final-layer correspondence and neuron permutations.Equal outputs would produce a smaller non-subnetwork network parametrizing zero, contradicting the induction hypothesis.
- Linear independence forces a bijection between corresponding penultimate neurons and determines the final weights up to a permutation matrix; induction then recovers permutations in earlier layers.The resulting transformations have the form Vi = PiWiP_(i−1)^T, with identity permutations at the input and output.
- Established conjecture cases yield unconditional identifiability for width-one networks and shallow networks, while layer-specific activations work when degrees increase recursively under stated bounds.For shallow networks, the sufficient degree condition is given as r ≥ 7d2 in the cited passage.
- With bias vectors, the argument would require linear independence of 1, σ(p1), …, σ(pk), a strengthening beyond the stated origin-passing setting.
5 Conclusion
The paper connects polynomial-composition linear independence with identifiability of polynomial MLPs and reports consequences for equivariant network design and model stitching. It frames complete identifiability for all polynomial MLP architectures as an open foundational direction.
- The paper relates generic polynomial MLP identifiability to a linear-independence problem for polynomial compositions.
- Established cases resolve identifiability for shallow MLPs and deep MLPs whose activation degrees grow from layer to layer.
- For architectures with full identifiability characterizations, equivariant network functions can be represented with every layerwise activation map equivariant.
- For the same architectures, sufficiently well-trained networks representing the same function can support model stitching after permutation alignment of internal neurons.
- A full resolution for all polynomial MLP architectures remains an open foundational problem that could follow from proving the paper’s conjectures or by other means.