where is small, , and . Notice that any such Boolean function can be viewed as a labeling function of strings of bits, and so learning the function from labeled instances amounts to a binary classification problem.
If we identify with , then the ‘s are essentially the big entries of the Walsh–Hadamard transform of , and these entries are indexed by the ‘s. As such, functions of the form are essentially the Boolean functions of concentrated spectra. These functions have been shown to well approximate the Boolean functions with sufficiently simple circuit implementations (e.g., see one, two, three), and given the strong resemblance between Boolean circuits and neural networks, the following hypothesis seems plausible:
Hypothesis. Boolean functions that are well approximated by learnable deep neural networks also enjoy a highly concentrated Walsh–Hadamard transform.
This hypothesis motivated our study, as it suggests that one doesn’t need to learn individual neurons, or even guess the underlying structure of the network (which has become quite an art form), but rather find a function of the form that matches the training set. Of course, this won’t work unless these functions satisfy a few of miracles:
1. Simple. The set of functions of the form needs to be sufficiently simple in order to generalize from the training set. To address this, we prove that the VC dimension of is .
2. Admits fast optimization. We need a fast algorithm that finds a member of that fits a given training set. This problem amounts to a mixture between the sparse fast Walsh–Hadamard transform and one-bit compressed sensing. Finding a scalable algorithm remains open, but we propose an algorithm that seems to do okay in small dimensions.
3. Models reality. We need to fit real-world labeling functions. Considering the broad applicability of deep neural networks, it suffices for our hypothesis to hold. In the paper, we also ran a convincing experiment, which I discuss below.
To test part 3 above, we applied our algorithm to the MNIST database of handwritten digits. Since our algorithm is slower in higher dimensions, we first processed the database by blurring, downsampling, and thresholding to produce images of on-and-off pixels:
Next, we ran our algorithm to find a member of that fits a training set of 8000 different zeros and ones, and then we tested this function on another collection of 3800 zeros and ones. We ended up with a misclassification rate of 0.74% after 160 seconds of training. The following depicts the 28 misclassified digits:
Can you distinguish the zeros from the ones? (See the paper for the solution.)
This experiment suggests a few conclusions. First, the function class meets requirements 1 and 3 from above in practice. Considering the depictions of misclassified digits, the classifier probably needs more resolution before it can perform better. This in turn requires an algorithm that scales better with . As such, it remains to tackle requirement 2 from above, that is, we need faster algorithms. See the conclusion of the paper for a few more open problems.