UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Relative loss bounds and polynomial-time predictions for the K-LMS-NET algorithm

Herbster, M; (2004) Relative loss bounds and polynomial-time predictions for the K-LMS-NET algorithm. In: Ben-David, S and Case, J and Maruoka, A, (eds.) Algorithmic Learning Theory: 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004: Proceedings. (pp. 309 - 323). Springer-Verlag: Berlin / Heidelberg, Germany. Green open access

Available under License : See the attached licence file.

Download (263kB)


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.

Type: Proceedings paper
Title: Relative loss bounds and polynomial-time predictions for the K-LMS-NET algorithm
ISBN: 3540233563
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-540-30215-5_24
Publisher version: http://dx.doi.org/10.1007/978-3-540-30215-5_24
Additional information: The original publication is available at www.springerlink.com
UCL classification: UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Engineering Science
URI: http://discovery.ucl.ac.uk/id/eprint/135667
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item