Constructive Bounds for the Topological Expressivity of Neural Networks

Özetle: The expressivity of a neural network $Φ$ describes the class of functions that a network can express.

Özet

The expressivity of a neural network $Φ$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $β(Φ^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $β(Φ(X))$. We formally prove that a ReLU network with architecture $(d,sumlimits_{k=1}^{d } β_k(3k+2),sumlimits_{k=1}^{d}β_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($β_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,…,d_N$ we achieve much better bounds $(sumlimits_{n=1} d_n, 3sumlimits_{n=1}limits^N d_n + 2N, sumlimits_{n=1}limits^N d_n + N) $ for Betti numbers given by $prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.

Orijinal Özet (İngilizce)

The expressivity of a neural network $Φ$ describes the class of functions that a network can express. The term topological expressivity refers to a family of measures particularly suited to understand binary classification and is often formulated in terms of the Betti numbers of a decision boundary $β(Φ^{-1}(0))$. Despite its popularity, this measure is not as useful for regression and other problems that do not involve a decision boundary. Instead, we propose to study topological expressivity in terms of the Betti numbers of the output of a neural network $β(Φ(X))$. We formally prove that a ReLU network with architecture $(d,sumlimits_{k=1}^{d } β_k(3k+2),sumlimits_{k=1}^{d}β_k(k+1))$ can express spaces homotopy equivalent to wedge sums of spheres with arbitrary Betti numbers. This gives upper bounds for any arbitrary connected ($β_0=1$) sequence of Betti numbers, but by constructing spaces homotopy equivalent to products of $N$ spheres of dimension $d_1,…,d_N$ we achieve much better bounds $(sumlimits_{n=1} d_n, 3sumlimits_{n=1}limits^N d_n + 2N, sumlimits_{n=1}limits^N d_n + N) $ for Betti numbers given by $prod_n (1+x^{d_n})$. Finally we conjecture a much stronger tight bound which gives the architectural bound $(d,d+1,d+1)$ for a space homeomorphic to the sphere.

Kaynak: arXiv:2610.13931 · PDF