How to build VLSI-efficient neural chips Page: 6 of 13
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Proposition 2 (from [54]). Arbitrary Boolean functions of
theformf: {0, 1n -+ { 0, 1) mcan be implemented in a neu-
ral network ofperceptrons restricted to fan-in 2 with a node
complexity of O {m 2n /(n + logm)} and requiring O (n)
layers.
One study [37] tried to unify these two lines of research
by first presenting analytical solutions for the general NN
problem in one dimension (having infinite size!), and then
giving practical solutions for the one-dimensional cases
(i.e., including an upper bound on the size). Extensions to
the n-dimensional case using three- and four-layers solu-
tions were derived under piecewise constant approxima-
tions (having constant or variable width partitions), and
under piecewise linear approximations (using ramps instead
of sigmoids).
As can been seen from these results, the known bounds
for size are exponential if NNs are used for solving general
problems (i.e., arbitrary BFs), but:
" they reveal a gap between the upper and the lower
bounds, thus encouraging research efforts to reduce
these gaps; and
" they suggest that, while still exponential (due to the
lower bounds), NNs with more layers (depth small
constant) might have a smaller size.
The only exception is given by Kolmogorov's superposi-
tions theorem which shows that there are NNs having only
2n + 1 neurons in the hidden layer which can approximate
any function.
2.2. Precision and Interconnectivity
Because most NNs are (and have been) simulated, two
aspects which have been neglected in too many cases are
the precision of weights and thresholds, and the fan-in of
the neurons. Only when hardware implementations of NNs
have been considered ([73] and the overview in [84]), pre-
cision and interconnectivity [1] became important.
Finite precision computation has started to be analysed
[52, 110, 117], and it was shown that in most cases several
bits suffice [14, 19, 84]. Even more, it was very recently
proven [8] that the generalisation error of NNs used for pat-
tern classification depends on the size of the weights (i.e.,
precision), rather than the number of weights. The result
presented there is that the misclassification probability con-
verges to an error estimate at rate of O ((cA) / hT). Here A
is the sum of the magnitude of the weights (2). The other pa-
rameters involved are: l is the number of layers, m is the
number of examples, and c is a constant. Beside supporting
heuristics that attempt to keep the weights small during
training (e.g., weight decay and early stopping), this also
suggests that NNs having more layers might converge
faster ! The magnitude of the weights (2) has already been
used as: (i) an optimum criteria for linear programming syn-
thesis [82]; (ii) for defining the minimal integer realisation
of one TG [55, 100, 116]; (iii) for minimising the area of
the VLSI implementations of NNs [19, 23, 24, 26]The other aspect of interconnectivity has been analysed
in relation to the area of a VLSI chip [46], where it was
shown that the area grows as the cube of the node's fan-in
(A3). Recently, the fact that AT2-optimal discrete NNs can
be obtained for small constantfan-ins was proven [17]. An-
other result for limited fan-in (A = 2) NNs was presented in
[54] (also as Proposition 2). An extension of that result to
arbitrary fan-ins was also suggested.
Proposition 3 (from [22). Arbitrary Boolean functions
f: {0, 1}n - {0, 1}m can be implemented in a neural net-
work of perceptrons restricted to fan-in A in O (n /logA)
layers.
Finally, the known weight bounds:
2(A-1)/2 < weight < (A+1)(A+1)/2/2A, (8)
hold for any fan-in A 4, show that we can expect to have a
precision of between A [86] and A logA bits per weight [53,
90, 94, 105, 106]. The upper bound is in fact slightly tighter
weigh > 1.618 [90], and this holds for any A ? 2.
As can be seen from (8), interconnectivity and precision
are interrelated, and fan-in also relates to depth, as smaller
fan-ins lead to deeper NNs (larger depths).
3. Entropy Bounds
The NN solving a classification problem has to 'encode'
the entropy of the data-set. It can be easily shown that such
an encoding exists. In [107] it is shown that shattering all
sets of m points in general position requires (m - 1) /2 pa-
rameters (i.e., weights). Another argument comes from a
classical AND-OR implementation for the data-set: each AND
gate has at most n inputs (one for each dimension), and
there are at most m / 2 AND gates; one more OR gate of (at
most) m/2 is needed. Because AND and OR gates encode
one bit per input (connection or no connection), the result-
ing Boolean circuit for solving a dichotomy problem has
nm /2+ m /2 = mn /2 bits.
A constructive upper bound on the needed number-of-
bits (denoted by #bits) has been obtained by following the
steps: (i) show that a uniform quantization of the n-dimen-
sional space-which satisfies the given classification prob-
lem (data-set)-always exists; (ii) determine the bounded
sub-space which is guaranteed to contain all the m exam-
ples; (iii) compute the number-of-bits.
Proposition 4 (from [12, 21]). The dichotomy of m exam-
ples from IR" can always be solved with:
#bits < 2 Fnlog (D/d) + 2.047n - (logn)/2 - 0.8251= 0 (mn) .
(9)
This shows that the entropy of the dichotomy of m exam-
ples from IRn is bounded by O (2mn), and remains un-
changed if there are k classes. The result has been obtained
using a whole ball Vyl~ (D, n) of radius D for upper bound-
ing the space containing all the examples.
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Beiu, V. How to build VLSI-efficient neural chips, article, February 1, 1998; New Mexico. (https://digital.library.unt.edu/ark:/67531/metadc698812/m1/6/: accessed April 23, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.