From: arms@cs.UAlberta.CA (Bill Armstrong)
Subject: Re: Interpolation and neural networks
Keywords: interpolation partition-of-unity
Organization: University of Alberta, Edmonton, Canada
Date: Fri, 14 Aug 1992 04:26:26 GMT

platt@synaptx.Synaptics.Com (John Platt) writes:

>In an article arms@cs.UAlberta.CA (Bill Armstrong) writes:
>>AN IMPORTANT QUESTION: Can anyone think of any other straightforward
>>ways to get bounds on values *between* test points?  The application
>>of NNs in safety-critical areas is at stake.

>  Yes.. It's quite straightforward and has already been suggested by
>Moody & Darken and separately by Kurt Stockbro for neural networks.
>It's a trick from approximation theory called "partition of unity" or
>sometimes a "generalized Shepard's method".

>  Normally, when you have a radial basis function network, the network
>output is a linear superposition of radial basis functions:

>       O_i = sum_j w_ij f_j(input) 

>  Moody & Darken suggest averaging the outputs, not summing them:

>             sum_j w_ij f_j(input)
>       O_i = ---------------------
>               sum_j f_j(input)

>That way, the output is always in the convex hull of the w_ij for any
>basis function f_j that is non-zero. If the f_j have local support, then
>you can bound the output vector in a region quite easily.

Some comments and references deleted...

True, at least as long as the basis functions are positive, you get a
bound related to the w_ij's, and even in some slightly broader
conditions.  In any region R_k of the input space where the same set
of f_js are the non-zero ones, the f_s are simply interpolating
between the associated w_ij vectors, and are more tightly bounded than
the convex hull of the set of all w_ij's.  I think you'll agree that
you need lots of j's to cover lots of regions with different
sufficiently small convex bounding sets to get accuracy in meeting a
spec.

I guess at this point on could ask whether this idea makes NNs safe,
or does it make approximation theory safe?  I don't see a role for BP
nets in this scheme for example.  Does anyone else?

On the other hand, I *do* see a role for ALNs.  Suppose you have 10^6
regions, then you could take, say, 20 ALNs and train them to compute a
20-bit number representing the region.  The boundaries won't be exact,
that doesn't matter.  The 20 bit number is used as an index to point
to a list of the j_s which can possibly be non-zero in the region
corresponding to those values of the 20 bits. Then you retrieve just
those f_j's, you calculate f_j(input) just for those, retrieve the
w_ij's for those same j's, do the products,add them, and divide by the
sum of those f_j(input).  If the lists are short, the calculation is
very efficient.

I guess this answer won't make any sense to the devotees of massive
parallelism, but it should make sense to those who have to compute
outputs with regard to speed and economy. Anyone who objects that
having to look up short, variable length lists of things is un-NN-like,
is welcome to his/her opinion.  I like RAM because it's cheap and is
essentially just combinational logic like trained ALNs.

Thanks for a really interesting answer to the question John!

Bill
--
***************************************************
Prof. William W. Armstrong, Computing Science Dept.
University of Alberta; Edmonton, Alberta, Canada T6G 2H1
arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071