Deep, super-narrow neural network is a universal classifier

Deep architecture models are known to be conducive to good generalisation for certain types of classification tasks. Existing unsupervised and semi-supervised training methods do not explain why and when deep internal representations will be effective. We investigate the fundamental principles of representation in deep architectures by devising a method for binary classification in multi-layer feed forward networks with limited breadth. We show that, given enough layers, a super-narrow neural network, with two neurons per layer, is capable of shattering any separable binary dataset. We also show that datasets that exhibit certain type of symmetries are better suited for deep representation and may require only few hidden layers to produce desired classification.