Multiple Threshold Neural Logic

Vasken Bohossian, Jehoshua BruckNeurIPS 1997

Introduction

In the study of artificial neural networks, the "Linear Threshold" (LT) gate serves as the standard Boolean model of a neuron. It computes a weighted sum of inputs and outputs a 1 if the sum exceeds a specific threshold. While LT circuits are more efficient than traditional AND/OR/NOT logic for certain arithmetic operations, they have significant limitations. For instance, a single LT gate cannot compute a simple parity function like XOR.

Furthermore, implementing symmetric functions in Very Large Scale Integration (VLSI) using standard 2-layer LT circuits introduces massive redundancy. Multiple gates in the first layer often compute the exact same weighted sum, only to compare it against different thresholds. This redundancy wastes valuable physical space on a chip. To solve this, researchers introduce the LTM (Linear Threshold with Multiple transitions) element, a powerful generalization of the standard Boolean neuron that captures the power of multiple thresholds in a single unit.

The LTM Element

The core "aha moment" of this research is realizing that moving multiple thresholds into the node itself eliminates the need to compute the same linear sum multiple times.

Mathematically, a standard LT gate is defined as $f(X) = \text{sgn}(w_0 + \sum w_i x_i)$. In contrast, an LTM gate is defined as: $$f(X) = h\left(\sum_{i=1}^{n} w_i x_i\right)$$ where $h$ is a function that can undergo a polynomial number of transitions (0 to 1, or 1 to 0) as the weighted sum increases.

Comparison of LT, SYM, and LTM gates

By computing the sum only once and allowing multiple transitions, LTM circuits achieve remarkable efficiency. For $n$-input symmetric Boolean functions, the VLSI layout area is reduced from $O(n^2)$ in traditional LT circuits to just $O(n)$ in LTM circuits. Additionally, a single layer of LTM gates can compute complex arithmetic, such as adding $m$ different $n$-bit integers (MADD) or multiplying integers (PRODUCT).

Computational Hierarchy and Power

Beyond circuit construction and area complexity, the paper uses threshold circuit theory to rigorously map where LTM sits within the hierarchy of Boolean function classes. The authors distinguish between standard LTM (which allows arbitrary weights) and $\widehat{LTM}$ (which restricts weights to polynomial growth).

Hierarchy of threshold circuit complexity classes

The theoretical analysis proves a strict hierarchy of inclusion: $\widehat{LT} \subset \widehat{LTM} \subset LTM \subset \widehat{LT}_2$. This places LTM strictly between 1-layer and 2-layer threshold circuits. Key function separations demonstrated in the paper include:

  • XOR: Can be computed in $\widehat{LTM}$ but not in standard $LT$.
  • Comparison (COMP): Exists in $LT$ but not in $\widehat{LTM}$, demonstrating that restricting LTM to small weights limits its ability to compute certain functions.
  • Inner Product mod 2 ($IP_k$): Requires two layers ($\widehat{LT}_2$) and cannot be computed by a single $LTM$ layer.

Hardware Realization and Future Work

LTM is not just a mathematical curiosity; it has practical implications for hardware design. The authors suggest that LTM can be implemented in analog VLSI using floating-gate transistors, where weights are stored as trapped electrons. They even note the fabrication of a programmable analog chip using $2\mu m$ technology to physically test the LTM model.

Future research directions include formally proving the conjecture that $\widehat{LT} = LT \cap \widehat{LTM}$, applying spectral techniques for deeper insights into LTM capabilities, and exploring PTM (Polynomial Threshold with Multiple transitions) for non-linear sums. Finally, scaling these programmable analog neural logic designs to modern nanometer processes remains an exciting open engineering challenge.

Summary updated

BibTeX
@inproceedings{bohossian1997multiple,
  author = {Vasken Bohossian and Jehoshua Bruck},
  title = {{Multiple Threshold Neural Logic}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}

Loading related content...

Figure