In this article we present new results on neural networks with linear
threshold activation functions. We precisely characterize the class of
functions that are representable by such neural networks and show that 2 hidden
layers are necessary and sufficient to represent any function representable in
the class. This is a surprising result in the light of recent exact
representability investigations for neural networks using other popular
activation functions like rectified linear units (ReLU). We also give precise
bounds on the sizes of the neural networks required to represent any function
in the class. Finally, we design an algorithm to solve the empirical risk
minimization (ERM) problem to global optimality for these neural networks with
a fixed architecture. The algorithm's running time is polynomial in the size of
the data sample, if the input dimension and the size of the network
architecture are considered fixed constants. The algorithm is unique in the
sense that it works for any architecture with any number of layers, whereas
previous polynomial time globally optimal algorithms work only for very
restricted classes of architectures. Using these insights, we propose a new
class of neural networks that we call shortcut linear threshold networks. To
the best of our knowledge, this way of designing neural networks has not been
explored before in the literature. We show that these neural networks have
several desirable theoretical properties.

本文研究了使用线性阈值激活函数的神经网络，探究了这种类型的函数可以被表示的范围，证明了用两层隐藏层可以表示任何在这个范围内的函数。同时提出了一种算法，用于解决这种类型神经网络的经验风险最小化问题，可以在多项式时间内进行。基于这些研究发现，我们提出了一种新型神经网络 —— 快捷线性阈值网络。