Authors: Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon
Organizations: Department of Applied Mathematics and Statistics, Colorado School of Mines, Golden, CO, USA · Department of Mathematics & Statistics, Air Force Institute of Technology, Wright-Patterson AFB, OH, USA · Department of Mathematics, Colorado State University, Fort Collins, CO, USA · Department of Mathematics, The Ohio State University, Columbus, OH, USA · Translational Data Analytics Institute, The Ohio State University, Columbus, OH
We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector x of active features is encoded through an overcomplete dictionary W, and feature recovery is performed by applying ReLU(W⊤Wx+b) with an appropriate bias vector b. We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order d/logn. In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with n>d+1, we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization---which should be of independent interest to frame theorists---of the distribution of signs in the Gram matrix.
Figures & tables
Figure 1: Left: Every color represented by nonnegative linear combinations of the vectors (1,0) and (0,1) , which represent red and blue, respectively. Middle: Every color represented by nonnegative linear combinations of at most two of the vectors (1,0) , (−1/2,3/2) , and (−1/2,−3/2) , which represent red, green, and blue, respectively. Right: Different saturations of the same hue that are all represented by the same vector as a (in general not 2 -sparse) linear combination of (1,0) , (−1/2,3/2) , and (−1/2,−3/2) , namely, (1/3,0) . A 2 -sparsity assumption ensures unique representation, but also that not all colors are representable. In this case, only the darkest shade in the color bar is representable. An interactive version can be viewed at https://miv.name/web-tools/color-superposition.html
Figure 2: Intuition for superposition. Start with a nonnegative k -sparse vector x . In this case, k=1 and x∈{(1,0),(0,1)} . Left: Assume W⊤W is close to the identity matrix in some sense, e.g., the columns of W form an equiangular tight frame. Then W⊤Wx can be interpreted as a noisy version of x , i.e., it resides in the blue disk about x . Middle left: Shift this disk by adding the bias vector b , which tends to be close to a negative multiple of the all–ones vector. Middle right: At this point, we apply ReLU, which has the effect of projecting the disk onto the nonnegative orthant. In our case, the nonzero entries in x were large relative to the noise added by applying W⊤W , and the effect is that every point in this projection has the same support as x . Right: If we care about recovering x , not just its support, we can rescale the result so that it’s close to x . Since ReLU is positively homogeneous, one can avoid rescaling after the ReLU by instead taking W←α⋅W and b←α⋅b .
Figure 3: Visualization of superposition. Top left: Start with a k -sparse binary vector x . In this case, k=6 and x∈R50 . Top right: Fix a 25×50 equiangular tight frame W that is centered , meaning the column vectors sum to the zero vector. We plot the entries of W⊤Wx and the threshold θ:=6/7 as a dashed line. The entries above this threshold form the support of x . Bottom left: Taking b:=−θ⋅\mathbbm1 , then ReLU(W⊤Wx+b) has the same support as x , but the entries are smaller. Bottom right: Multiplying by α:=7/3 makes the nonzero entries closer to 1 . Since ReLU is positively homogeneous, one can avoid rescaling after the ReLU by instead taking W←α⋅W and b←α⋅b .