Neural Network Training with Approximate Logarithmic Computations (lnsdnn)

TL;DR — Multipliers dominate the cost of the multiply-accumulate units that train neural networks. In the logarithmic number system (LNS) a multiply is just an add, so we run all of training and inference in the log domain and approximate the one hard part, log-domain addition, with a 20-entry look-up table or plain bit-shifts. With 16-bit fixed-point words, the log-domain network lands within about 1% of floating point on four image datasets.

Plot of the exact log-domain correction terms Delta-plus and Delta-minus against d, with a 20-entry look-up table at resolution one half and the bit-shift approximation overlaid as step functions.

Figure 1. The correction terms Δ₊(d) and Δ₋(d) that make log-domain addition hard, with the look-up table (r = ½) and bit-shift approximations that replace them.

Abstract

The high computational complexity associated with training deep neural networks limits online and real-time training on edge devices. This paper proposed an end-to-end training and inference scheme that eliminates multiplications by approximate operations in the log-domain which has the potential to significantly reduce implementation complexity. We implement the entire training procedure in the log-domain, with fixed-point data representations. This training procedure is inspired by hardware-friendly approximations of log-domain addition which are based on look-up tables and bit-shifts. We show that our 16-bit log-based training can achieve classification accuracy within approximately 1% of the equivalent floating-point baselines for a number of commonly used datasets.

In the log domain, multiplying is the easy part

LNS stores a real number v as the base-2 logarithm of its magnitude, V = log₂|v|, plus its sign s_v. Multiplication and exponentiation get cheaper; addition gets harder, because the result needs a correction term that depends on how far apart the two operands are.

Multiply → add

U = X + Y

The output sign is the XNOR of the input signs. No multiplier needed.

Add → max plus a correction

Z = max(X, Y) + Δ_±(|X − Y|)

Δ₊(d) = log₂(1 + 2^−d) when the signs match, Δ₋(d) = log₂(1 − 2^−d) when they differ. This is the term to approximate.

Exponentiate → multiply

w = x^y ↔ W = yX

For a positive base x; used for the soft-max. Subtraction is addition with the second sign flipped.

$A log-domain fixed-point word: a sign bit and qi integer bits and qf fraction bits holding log2 of the magnitude, followed by the sign bit s_x of the number.$

A fixed-point LNS word: log₂|x| as a signed number with q_i integer and q_f fraction bits, plus the sign bit s_x, for W_log = 2 + q_i + q_f bits in total.

Two cheap approximations of log-domain addition

Training is already noisy (stochastic gradients, finite precision), so the question is how crude the Δ approximation can get before accuracy suffers.

Look-up table

Sample Δ_±(d) over the range [0, d_max] at resolution r, i.e. 1/r points per unit interval, for a table of d_max/r entries. Sweeping both, d_max = 10 and r = ½ were enough: a 20-entry table for every operation. The soft-max proved more sensitive and uses a 640-entry table (r = 1/64).

Bit-shifts

Using ln(1 ± x) ≈ ±x for small x, the corrections become powers of two: Δ₊(d) ≈ 1·2^−d and Δ₋(d) ≈ −1.5·2^−d, which is just a shift. This generalizes an earlier bit-shift scheme to signed arithmetic, and it is equivalent to a look-up table with r = 1.

End-to-end training in the log domain

Matrix products map directly onto the operations above. The remaining pieces of training each get a log-domain form.

Activation: log-leaky ReLU

Leaky ReLU becomes llReLU: positive inputs pass through, negative ones get β added to their log magnitude. One hyper-parameter, and its derivative is equally simple in the log domain.

Weight initialization

A symmetric initial distribution f_w maps to a Bernoulli sign and log magnitudes drawn from f_W(y) = 2^y+1 ln 2 · f_w(2^y), so weights start in the log domain directly.

Soft-max and cross-entropy

The soft-max and its gradient initialization p − y are written with log-domain exponentiation, addition and subtraction.

Fixed-point bit-width

A worst-case analysis says matching a 16-bit linear format (4 integer, 11 fraction bits) needs a 21-bit log word. In practice the experiments show the same width as the linear domain suffices.

Inputs are converted to the log domain offline in floating point; in a real-time system that conversion could use the same approximate operations.

Results

≤ 1.4

points of test accuracy between 16-bit log-domain training and floating point, on all four datasets

20

table entries approximate every log-domain add (640 for the soft-max)

16 bits

fixed-point log words, the same width as the linear baseline

× → +

every multiply in the multiply-accumulates becomes an add

Dataset	Float	Linear, fixed-point		Log, look-up table		Log, bit-shifts
Dataset	Float	12b	16b	12b	16b	12b	16b
MNIST	97.4	97.3	96.9	96.0	97.2	95.5	96.5
Fashion-MNIST	87.1	82.8	88.0	80.5	87.1	79.3	85.7
EMNIST-Digits	98.6	98.3	98.7	96.9	97.5	96.2	97.4
EMNIST-Letters	88.1	79.7	88.7	76.4	86.7	73.7	82.5

Table 1. Test accuracy (%) after 20 epochs. The log-domain columns approximate log-domain addition with the look-up table or with bit-shifts. 16-bit words use 11 fraction bits in the linear domain and 10 in the log domain (one bit goes to the sign); 12-bit words use 7 and 6. The network is an MLP with 784 inputs, one hidden layer of 100 neurons and a soft-max output, trained by SGD (mini-batch 5, learning rate 0.01).

Learning curves

MNIST validation accuracy over 20 epochs for linear and log-domain training at 12 and 16 bits.

Figure 2. Validation accuracy for 12- and 16-bit log-domain training against 12- and 16-bit linear training. Log-domain runs use the 20-entry table for all operations except the soft-max (640 entries).

Talk

ICASSP 2020 presentation. Slides (PDF).

Code

arnabsanyal/lnsdnn has the log-domain core in C (an OpenMP log-multiplier with a Python wrapper) and MLP experiments for all four datasets, in floating and fixed point, in both the linear and log domains. Trained models are stored with Git LFS.

conda env create -f setup/environment.yml
conda activate lnsdnn
cd src && python setup.py install
cd 3_log_floatingpoint/mnist
python download_data.py               # fetch the dataset (see note below)
python train.py                      # inference with the included model
python train.py --is_training True   # train from scratch

The release is still in progress: the bit-shift experiments are not yet in the repository, and the dataset downloads need re-hosting. The README tracks what is left.

Scope and limitations

Small networks. The experiments train one-hidden-layer MLPs; larger convolutional networks are future work.
Hardware cost is not measured. The approach only pays off if the approximate log-domain adder is substantially cheaper in silicon than a multiplier. Co-optimizing the Δ approximation for accuracy and circuit complexity is future work.
12 bits is not enough everywhere. At 12 bits, log-domain accuracy drops noticeably on Fashion-MNIST and EMNIST-Letters (Table 1); 16 bits closes the gap.

BibTeX

@inproceedings{sanyal2020neural,
  author    = {Sanyal, Arnab and Beerel, Peter A. and Chugg, Keith M.},
  title     = {{Neural Network Training with Approximate Logarithmic Computations}},
  booktitle = {ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  year      = {2020},
  pages     = {3122--3126},
  doi       = {10.1109/ICASSP40776.2020.9053015}
}

This work was supported in part by the National Science Foundation (CCF-1763747).