Performance Guarantees and Approximate Computations for a
two-layer ``Artificial Neural Network'' with Uncountable Hidden Units
Mark Herbster
University College, London
We consider a two-layer network algorithm. The first layer consists
of an uncountable number of linear units. Each linear unit is an
LMS algorithm whose inputs are first ``kernelized.'' Each
unit is indexed by the value of a parameter corresponding to a
parameterized reproducing kernel. The first-layer outputs are then
connected to an "exponential weights" algorithm which combines
them to produce the final output. We give loss bounds for
this algorithm; and for specific applications to prediction
relative to the best convex combination of kernels, and the best
width of a Gaussian kernel.
The algorithm's predictions require the computation of an
expectation which is a quotient of integrals as seen in a variety of
Bayesian inference problems. Typically this computational problem
is tackled by MCMC, importance sampling, and other sampling
techniques for which there are few polynomial time guarantees of the
quality of the approximation in general and none for our problem
specifically. We develop a novel deterministic polynomial time
approximation scheme for the computations of expectations considered
in this paper.
