This paper, published in the early 1990s, presents a clever mathematical workaround to bridge the gap between standard neural network algorithms and specialized parallel hardware. By leveraging the geometric properties of high-dimensional spaces, the authors demonstrate how to run Multilayer Perceptrons (MLPs) on hardware that wasn't originally designed for them, achieving massive throughput without sacrificing accuracy.
The Dot Product Bottleneck
In the early 90s, the primary bottleneck for neural network performance was the "dot product." Standard MLPs rely heavily on calculating the dot product between input vectors and weights. In hardware (VLSI), implementing these requires a large number of multiplication units, which are expensive in terms of chip real estate and power.
The Intel Ni1000 chip was a state-of-the-art neural processor at the time, but it was designed for Radial Basis Function (RBF) networks. To maximize speed and parallelism, the Ni1000 was built to calculate "city block" distances ($l_1$-norm) instead of Euclidean dot products, effectively avoiding the need for complex multipliers. The challenge Perrone and Cooper tackled was: How can we run a standard MLP on a chip that cannot efficiently compute dot products?
The City Block MLP
The authors introduced the City Block MLP. The core innovation is a two-step mathematical transformation:
- Dot Product as Norms: They rewrote the standard dot product formula using the polarization identity: $$\vec{x} \cdot \vec{y} = \frac{1}{4}(\|\vec{x} + \vec{y}\|^2 - \|\vec{x} - \vec{y}\|^2)$$
- The $l_1$ Approximation: They observed that in high-dimensional spaces ($n$), the Euclidean length ($l_2$-norm) can be accurately approximated by the City Block length ($l_1$-norm) using a scaling factor: $$\|z\|_2 \approx \frac{1}{\sqrt{n}} |z|_1$$
By substituting the $l_1$ approximation into the norm-based dot product formula, they created a version of the MLP that the Ni1000 could calculate using its native, high-speed parallel architecture. While the forward pass uses this approximation, the authors initially kept the backward pass (training) identical to standard backpropagation to simplify the implementation.
The Blessing of Dimensionality
Usually, high dimensionality in machine learning is seen as a "curse." Here, it is a blessing. The authors showed that as the number of dimensions ($n$) increases, the variance of the error in the $l_1 \approx l_2$ approximation drops significantly.
In spaces with 100 or more dimensions, the approximation becomes remarkably stable. Instead of forcing the hardware to perform standard math, the authors successfully modified the algorithm to fit the hardware's strengths.
Datasets and Key Results
The researchers evaluated their "City Block" approach on two primary real-world tasks:
- NIST Handwritten OCR: A 120-dimensional representation of handwritten digits and letters (Numbers, Lowercase, and Uppercase).
- Human Face Recognition: A grayscale image database with a much higher dimensionality of 2294.
The Ni1000 architecture allowed for roughly 40,000 classifications per second for 256-dimensional inputs.
While the $l_1$ approximation introduces a slight performance hit, the City Block MLP performed nearly as well as the standard version. For example, on the Face dataset, the standard MLP achieved 94.6% accuracy, while the City Block version achieved 92.2%.
To counter this minor drop, the authors used ensemble averaging—combining the outputs of multiple networks. When using an ensemble of City Block MLPs, the accuracy on the Face dataset jumped to 96.3%, surpassing the single standard MLP. Similar improvements were observed across the NIST OCR datasets.
Limitations and Future Work
- Approximation Error: While small in high dimensions, the approximation is still an approximation. The "City Block" version is consistently slightly less accurate than a standard MLP when compared one-to-one.
- Simplified Backprop: In this paper, the authors used the standard derivative for backpropagation rather than the exact derivative of the City Block approximation. They noted that using the "correct" derivative in future simulations might further improve performance.
- Layer Limitations: The authors primarily applied the approximation to the first layer of weights (where dimensionality is highest). They suggested that for very large networks, applying it to subsequent layers would be necessary to maintain the speed advantage.
Summary updated