Modern neural network architectures use structured linear transformations,
such as low-rank matrices, sparse matrices, permutations, and the Fourier
transform, to improve inference speed and reduce memory usage compared to
general linear maps. However, choosing which of the myriad structured
transformations to use (and its associated parameterization) is a laborious
task that requires trading off speed, space, and accuracy. We consider a
different approach: we introduce a family of matrices called kaleidoscope
matrices (K-matrices) that provably capture any structured matrix with
near-optimal space (parameter) and time (arithmetic operation) complexity. We
empirically validate that K-matrices can be automatically learned within
end-to-end pipelines to replace hand-crafted procedures, in order to improve
model quality. For example, replacing channel shuffles in ShuffleNet improves
classification accuracy on ImageNet by up to 5%. K-matrices can also simplify
hand-engineered pipelines -- we replace filter bank feature computation in
speech data preprocessing with a learnable kaleidoscope layer, resulting in
only 0.4% loss in accuracy on the TIMIT speech recognition task. In addition,
K-matrices can capture latent structure in models: for a challenging permuted
image classification task, a K-matrix based representation of permutations is
able to learn the right latent structure and improves accuracy of a downstream
convolutional model by over 9%. We provide a practically efficient
implementation of our approach, and use K-matrices in a Transformer network to
attain 36% faster end-to-end inference speed on a language translation task.

我们引入了一种矩阵系列，叫做 Kaleidoscope matrices（K-matrix），它可以在保持时间和空间复杂度基本上不变的前提下，有效地捕捉模型中的结构特征。我们利用该方法，在端到端学习中自动学习了结构变换，实现了模型优化。实验结果表明，我们的方法可以用较小的计算代价比传统方法更好地捕捉结构特征，从而获得更高的效果。