Regression Estimation with Support Vector Learning Machines (cid:0) Alexander Smola in collaboration with (cid:1) Chris Burges (cid:2) Harris Drucker (cid:3) Steve Golowich (cid:4) Leo van Hemmen (cid:5) Klaus(cid:0)Robert Mu(cid:1)ller (cid:6) Bernhard Sch(cid:1)olkopf (cid:7) Vladimir Vapnik December (cid:2)(cid:3)(cid:4) (cid:3)(cid:5)(cid:5)(cid:6) Version (cid:3)(cid:7)(cid:8)(cid:3) (cid:0) Physik Department(cid:0) Technische Universit(cid:1)at Mu(cid:1)nchen (cid:1) Lucent Technologies(cid:0) Holmdel (cid:2) Lucent Technologies(cid:0) Holmdel (cid:3) Princeton University(cid:0) Princeton (cid:4) Physik Department(cid:0) Technische Universit(cid:1)at Mu(cid:1)nchen (cid:5) GMD First(cid:0) Berlin (cid:6) Max Planck Institut fu(cid:1)r biologische Kybernetik (cid:7) AT(cid:2)T Research(cid:0) Holmdel (cid:0) Support Vector Learning Machines (cid:1)SVLM(cid:2) have become an emerging technique which has proven successful in many traditionally neural network dominated ap(cid:3) plications(cid:4) This is also the case for Regression Estimation (cid:1)RE(cid:2)(cid:4) In particular we are able to construct spline approximations of given data independently from the number of input(cid:3)dimensions regarding complexity during training and with only linear complexity for reconstruction (cid:3) compared to exponential complexity in conventional methods(cid:4) I would like to thank Yann LeCun(cid:5) Patrick Ha(cid:6)ner(cid:5) Martin Hasler(cid:5) Darshyang Lee(cid:5) Noboru Murata(cid:5) Craig Nohl(cid:5) Patrice Simard(cid:5) Charles Stenard and Pascal Vincent for many inspiring discussions(cid:4) This project was made possible through funding by ARPA and the GNSF(cid:4) A This text was created with LTEX(cid:0)(cid:0) using the document class article and the german package(cid:1) It can be downloaded from http(cid:2)(cid:3)www(cid:1)(cid:4)rst(cid:1)gmd(cid:1)de(cid:3)(cid:5)smola Contents (cid:0) A Roadmap (cid:1) (cid:7)(cid:4)(cid:0) How to read this Thesis (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8) (cid:7)(cid:4)(cid:9) A Short Review of Approximation and Regression Estimation (cid:4) (cid:4) (cid:10) (cid:7)(cid:4)(cid:11) The Reason for Support Vectors (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:12) (cid:2) Introduction (cid:2)(cid:0) (cid:0)(cid:4)(cid:0) The Regression Problem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:7) (cid:0)(cid:4)(cid:9) A Special Class of Functions (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:0) (cid:0)(cid:4)(cid:9)(cid:4)(cid:0) Least Mean Square Fitting (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:0) (cid:0)(cid:4)(cid:9)(cid:4)(cid:9) Ridge Regression (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:9) (cid:0)(cid:4)(cid:11) Linear Support Vectors (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:11) (cid:0)(cid:4)(cid:13) The Lagrange Function and Wolfe(cid:14)s Dual (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:13) (cid:0)(cid:4)(cid:15) Karush(cid:3)Kuhn(cid:3)Tucker theorem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:8) (cid:0)(cid:4)(cid:8) The Dual Support Vector Problem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:8) (cid:3) Loss Functions (cid:2)(cid:4) (cid:9)(cid:4)(cid:0) Maximum Likelihood Estimators (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:12) (cid:9)(cid:4)(cid:9) Common Density Models (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:16) (cid:9)(cid:4)(cid:9)(cid:4)(cid:0) Gauss (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:16) (cid:9)(cid:4)(cid:9)(cid:4)(cid:9) Laplace (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:16) (cid:9)(cid:4)(cid:9)(cid:4)(cid:11) Huber (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:7) (cid:9)(cid:4)(cid:9)(cid:4)(cid:13) (cid:1)(cid:3)insensitive Loss Function (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:7) (cid:9)(cid:4)(cid:11) Solving the Optimization Equations (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:0) (cid:9)(cid:4)(cid:11)(cid:4)(cid:0) Polynomial Loss Functions (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:13) (cid:9)(cid:4)(cid:11)(cid:4)(cid:9) Piecewise Polynomial and Linear Loss Function (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:15) (cid:9)(cid:4)(cid:11)(cid:4)(cid:11) Local Loss Functions (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:10) (cid:5) Kernels (cid:3)(cid:4) (cid:11)(cid:4)(cid:0) Nonlinear Models (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:12) (cid:11)(cid:4)(cid:9) Mercer(cid:14)s Condition (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:16) (cid:11)(cid:4)(cid:11) Some Useful Kernels (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:7) (cid:11)(cid:4)(cid:13) Intermediate Mapping (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:7) (cid:11)(cid:4)(cid:15) Tensor Products (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:0) (cid:9) CONTENTS (cid:11) (cid:11)(cid:4)(cid:8) Direct Mapping into Hilbert Space (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:9) (cid:6) Optimizer (cid:5)(cid:7) (cid:13)(cid:4)(cid:0) A Class of QP(cid:3)Problems (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:10) (cid:13)(cid:4)(cid:9) An Equivalent Formulation(cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:12) (cid:13)(cid:4)(cid:11) Classical Optimizers (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:16) (cid:13)(cid:4)(cid:11)(cid:4)(cid:0) Projected Gradient Descent (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:16) (cid:13)(cid:4)(cid:11)(cid:4)(cid:9) Conjugate Gradient Descent (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:7) (cid:13)(cid:4)(cid:13) Interior Point Methods (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:7) (cid:13)(cid:4)(cid:13)(cid:4)(cid:0) Primal Problem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:0) (cid:13)(cid:4)(cid:13)(cid:4)(cid:9) Dual Problem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:0) (cid:13)(cid:4)(cid:13)(cid:4)(cid:11) Central Path (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:9) (cid:13)(cid:4)(cid:13)(cid:4)(cid:13) Predictor (cid:17) Corrector (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:9) (cid:13)(cid:4)(cid:13)(cid:4)(cid:15) Modi(cid:18)ed Levinson Decomposition (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:13) (cid:13)(cid:4)(cid:13)(cid:4)(cid:8) Computing (cid:2) and other updates (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:8) (cid:8) Experiments (cid:6)(cid:4) (cid:15)(cid:4)(cid:0) Approximation (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:12) (cid:15)(cid:4)(cid:0)(cid:4)(cid:0) Number of Support Vectors (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:0) (cid:15)(cid:4)(cid:9) Regression (cid:17) Estimation (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:0) (cid:15)(cid:4)(cid:9)(cid:4)(cid:0) Number of Support Vectors (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:11) (cid:15)(cid:4)(cid:9)(cid:4)(cid:9) Optimal Choice of Parameters (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:13) (cid:15)(cid:4)(cid:9)(cid:4)(cid:11) Asymptotic E(cid:19)ciency (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:16) (cid:15)(cid:4)(cid:11) Future Perspectives (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:0) (cid:1) Summary (cid:1)(cid:8) A Implementation (cid:1)(cid:1) A(cid:4)(cid:0) Choice of a programming language (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:8) A(cid:4)(cid:9) Class Libraries (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:10) A(cid:4)(cid:9)(cid:4)(cid:0) Linear Algebra Package (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:10) A(cid:4)(cid:9)(cid:4)(cid:9) Data Visualization (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:12) A(cid:4)(cid:9)(cid:4)(cid:11) Optimization (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:16) B MPS Format (cid:7)(cid:2) B(cid:4)(cid:0) The Problem (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:10)(cid:0) B(cid:4)(cid:9) The File (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:10)(cid:0) B(cid:4)(cid:9)(cid:4)(cid:0) Keywords (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:10)(cid:9) B(cid:4)(cid:9)(cid:4)(cid:9) Listing (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:10)(cid:9) List of Figures (cid:0)(cid:4)(cid:0) sample data and corresponding (cid:20)attest (cid:18)t (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:0)(cid:13) (cid:9)(cid:4)(cid:0) L(cid:1) loss function and corresponding density (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:7) (cid:9)(cid:4)(cid:9) L(cid:0) loss function and corresponding density (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:0) (cid:9)(cid:4)(cid:11) Huber loss function and corresponding density (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:9) (cid:9)(cid:4)(cid:13) (cid:1)(cid:3)insensitive loss function and corresponding density (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:9)(cid:11) (cid:11)(cid:4)(cid:0) B(cid:3)Splines of degree (cid:7) up to (cid:15) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:15) (cid:11)(cid:4)(cid:9) AutocorrelationFunctionforanaudiosignal(cid:21) (cid:22)FischersFritz(cid:18)scht frische Fische(cid:23) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:8) (cid:13)(cid:4)(cid:0) Boundary Constraints on (cid:3) and (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:11)(cid:16) (cid:15)(cid:4)(cid:0) sincx(cid:5) datapoints with (cid:1)(cid:3)precision and approximations with (cid:7)(cid:5)(cid:0)(cid:5) (cid:7)(cid:5)(cid:9)(cid:5) (cid:7)(cid:5)(cid:15) and (cid:0)(cid:5)(cid:7) precision using a spline kernel of degree (cid:11) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:13)(cid:16) (cid:15)(cid:4)(cid:9) sinc x measured at (cid:0)(cid:7)(cid:7)iidlocationswitha splineapproximation jj jj of degree (cid:0) and precision (cid:7)(cid:4)(cid:0) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:7) (cid:15)(cid:4)(cid:11) forces (cid:1)red(cid:2) exerted by the (cid:1)(cid:3)tube (cid:1)green(cid:2) on the approximation (cid:1)blue(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:0) (cid:15)(cid:4)(cid:13) approximationwith (cid:0)(cid:4)(cid:7)(cid:5) (cid:7)(cid:4)(cid:15)(cid:5) (cid:7)(cid:4)(cid:9)(cid:5) (cid:7)(cid:4)(cid:0)(cid:5) (cid:7)(cid:4)(cid:7)(cid:15)and (cid:7)(cid:4)(cid:7)(cid:9) precision preci(cid:3) sion using a B(cid:3)spline kernel of degree (cid:11)(cid:5) the solid dots are support vectors (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:9) (cid:15)(cid:4)(cid:15) Number of Support Vectors vs(cid:4) precision of the approximation (cid:1)spline approximation of degree (cid:0) with (cid:0)(cid:7)(cid:7) nodes(cid:2) for (cid:0)(cid:7)(cid:7) data(cid:3) points (cid:1)note that the maximum number of points is (cid:0)(cid:7)(cid:7)(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:11) (cid:1) (cid:15)(cid:4)(cid:8) regression (cid:17) estimation of (cid:7)(cid:5)(cid:16)sinc(cid:1)(cid:0)(cid:7)x(cid:2) on (cid:24)(cid:7)(cid:6) (cid:0)(cid:25) for (cid:0)(cid:7)(cid:7) samples with gaussian noise of standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:7)(cid:4)(cid:9)(cid:5) (cid:7)(cid:4)(cid:15) and (cid:0)(cid:4)(cid:7) and the corresponding (cid:1)(cid:3)insensitive loss(cid:3)zone of width (cid:7)(cid:4)(cid:0)(cid:5) (cid:7)(cid:4)(cid:9)(cid:5) (cid:7)(cid:4)(cid:15) and (cid:0)(cid:4)(cid:7) (cid:1)black dots are support vectors(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:13) (cid:15)(cid:4)(cid:10) Number of Support Vectors depending on the (cid:1)(cid:3)margin for (cid:18)xed noise level and probability of a point to lie outside the margin for an unbiased estimator and noise level (cid:7) (cid:26) (cid:7)(cid:5)(cid:9) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:15) (cid:13) LIST OF FIGURES (cid:15) (cid:15)(cid:4)(cid:12) Number of Support Vectors for di(cid:6)erent noise levels and (cid:18)xed (cid:1)(cid:3) margin of (cid:7)(cid:5)(cid:9) (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise(cid:5) (cid:9)(cid:15) trials(cid:2)and probabilityof a pointto lieoutside the margin for an unbiased estimator(cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:15) (cid:15)(cid:4)(cid:16) Number of Support Vectors depending on the regularization and the (cid:1)(cid:3)margin (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:8) (cid:15)(cid:4)(cid:0)(cid:7) (cid:1)(cid:3)insensitive cost function depending on the regularizationand the (cid:1)(cid:3)margin(cid:1)splines ofdegree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7)nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:8) (cid:15)(cid:4)(cid:0)(cid:0) L(cid:0)(cid:3)error ofthe approximationdepending onthe regularizationand the (cid:1)(cid:3)margin (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:10) (cid:15)(cid:4)(cid:0)(cid:9) minimal L(cid:0)(cid:3)error (cid:1)optimal choice of the regularization(cid:2) depend(cid:3) ing on the (cid:1)(cid:3)margin (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:10) (cid:15)(cid:4)(cid:0)(cid:11) L(cid:1)(cid:3)error ofthe approximationdepending onthe regularizationand the (cid:1)(cid:3)margin (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:12) (cid:15)(cid:4)(cid:0)(cid:13) minimal L(cid:1)(cid:3)error (cid:1)optimal choice of the regularization(cid:2) depend(cid:3) ing on the (cid:1)(cid:3)margin (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise with standard deviation (cid:7)(cid:4)(cid:0)(cid:5) (cid:9)(cid:8) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:15)(cid:12) (cid:15)(cid:4)(cid:0)(cid:15) Asymptotic e(cid:19)ciency for an (cid:1)(cid:3)insensitive model and data with gaussian noise(cid:4) See equation (cid:1)(cid:15)(cid:4)(cid:0)(cid:11)(cid:2)(cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:7) (cid:15)(cid:4)(cid:0)(cid:8) L(cid:0)(cid:5) L(cid:1) and (cid:1)(cid:3)insensitive loss functions in comparison(cid:4) One can see thatthe (cid:1)(cid:3)insensitiveapproximatesthe L(cid:1) functionbetter thanthe L(cid:0) does (cid:1)piecewise linear (cid:18)t with one more parameter(cid:2)(cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:0) (cid:15)(cid:4)(cid:0)(cid:10) L(cid:0) and L(cid:1)(cid:3)error of the approximation for di(cid:6)erent noise levels and (cid:18)xed (cid:1)(cid:3)margin of (cid:7)(cid:5)(cid:9) (cid:1)splines of degree (cid:0)(cid:5) (cid:0)(cid:7)(cid:7) points(cid:5) (cid:0)(cid:7)(cid:7) nodes(cid:5) gaussian noise(cid:5) (cid:9)(cid:15) trials(cid:2) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:9) (cid:15)(cid:4)(cid:0)(cid:12) L(cid:0)(cid:3)error for di(cid:6)erent noise levels (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:9) (cid:15)(cid:4)(cid:0)(cid:16) L(cid:1)(cid:3)error for di(cid:6)erent noise levels (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:11) (cid:15)(cid:4)(cid:9)(cid:7) Optimal choice of (cid:1) for di(cid:6)erent noise levels (cid:1)(cid:0)(cid:7)(cid:7) samples(cid:2) and theoretically best value for the asymptotic unbiased case (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:11) A(cid:4)(cid:0) Structure of a matrix (cid:17) vector object (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:10) A(cid:4)(cid:9) main control window (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:12) A(cid:4)(cid:11) a typical session for (cid:0)D(cid:3)regression (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:4) (cid:8)(cid:16) Chapter (cid:0) A Roadmap The purpose of this text is threefold(cid:21) First it should be a documentation of the research done at Bell Laboratories(cid:5) Holmdel(cid:4) Secondly it should serve as an introduction to Support Vector Regression(cid:3)Estimation and (cid:18)nally it is written in order to obtain the degree of a (cid:22)Diplomingenieur der Physik(cid:23) at the Technische Universita(cid:27)t Mu(cid:27)nchen(cid:4) Of course these goals may sometimes not be consistent(cid:4) Hence the reader may skip some chapters and focus on other ones to get the information he needs(cid:4) I tried to make the chapters as self contained as possible without repeating tedious details(cid:4) (cid:0)(cid:1)(cid:2) How to read this Thesis Chapter (cid:0) contains a short overview over some basic regression techniques and explains the fundamental ideas of linear Support Vector function approximation including basic knowledge about convex programming necessary for solving the optimization equations involved(cid:4) The reader may skip the parts not directly concerning Support Vectors as these are just for giving a motivation for the setting of the problem(cid:4) In chapter (cid:9) I will show how Support Vector Machines can be extended to the case of Regression(cid:17)Estimation with noisy data(cid:4) A set of di(cid:6)erent loss functions and their implications on the robustness of the estimation will be presented with an explicit derivation of the corresponding optimization functionals(cid:4) For a brief overview it may su(cid:19)ce to read the section about (cid:1)(cid:3)insensitive loss functions only(cid:4) The next chapter describes a way of porting the ideas on Linear Support Vec(cid:3) tor Regression to nonlinear models(cid:4) The approach is similar to nonlinear Sup(cid:3) port Vector pattern recognition following the concept of (cid:24)ABR(cid:8)(cid:13)(cid:25) and (cid:24)BGV(cid:16)(cid:9)(cid:25) of mapping to a highdimensional space where linear calculations are performed(cid:4) For a reader already familiar with this concept and for a quick review of the methods employed the sections (cid:11)(cid:4)(cid:13) and (cid:11)(cid:4)(cid:15) may be enough(cid:4) A general method of constructing nonlinear regression systems is given in (cid:11)(cid:4)(cid:8)(cid:4) (cid:8) CHAPTER (cid:6)(cid:1) A ROADMAP (cid:10) Chapter (cid:13) describes the moreimplementationspeci(cid:18)c solutionsofthe support vector system(cid:4) Basically any quadratic programmingalgorithm could be used for solving the problem although di(cid:6)erent methods may show varying performance due to the setting of the problem(cid:4) An exemplary solution is shown for interior point methods following the ideas of (cid:24)Van(cid:16)(cid:13)(cid:25)(cid:4) Furthermore this chapter contains a method for e(cid:19)ciently solving Toeplitz(cid:3)like systems by a modi(cid:18)ed Levinson method(cid:4) Experimental results on the performance of Support Vector Regression are given in chapter (cid:15)(cid:4) Further information may be obtained from (cid:24)VGS(cid:16)(cid:8)(cid:25) and (cid:8) (cid:24)DBK (cid:16)(cid:8)(cid:25)(cid:4) Finally appendix A concludes this work by describing some of the implemen(cid:3) tation issues of Support Vector learning machines(cid:4) This may be relevant for somebody trying to model a similar system only(cid:4) Hence most of the readers will want to skip it(cid:4) Appendix B contains a brief de(cid:18)nition of the industry standard MPS (cid:18)le format(cid:4) (cid:0)(cid:1)(cid:3) A Short Review of Approximation and Re(cid:4) gression Estimation The simplest way of approximating a function (cid:1)and the crudest one(cid:5) too(cid:2) would be to approximate it by its mean in the domain of interest(cid:4) A more sophisticated approach would be to choose linear functions or more complicated bases of func(cid:3) tions to achieve this goal(cid:4) Increasing the complexity of the base seems to be the solution to obtain better results(cid:4) But this is not really true as one will encounter the well known e(cid:6)ect of (cid:14)over(cid:28)(cid:18)tting(cid:14)(cid:5) which means that the complexity of the system of functions used is too high(cid:4) Since Schoenberg(cid:14)s pioneering paper (cid:24)Sch(cid:13)(cid:8)(cid:25) on spline approximation consist(cid:3) ing of l(cid:3)times di(cid:6)erentiable piecewise polynomial functions combined with a set of smoothness (cid:1)and regularity(cid:2) constraints have been investigated in great detail (cid:24)PTVF(cid:16)(cid:9)(cid:25)(cid:5) (cid:24)SB(cid:16)(cid:11)(cid:25)(cid:4) This approach has proven to be e(cid:6)ective in the case of low(cid:3) dimensionalfunctionsonlyasthenumberofcoe(cid:19)cients increases exponentionally with dimensionality thereby virtually imposing a limit of four dimensions in real world applications(cid:4) Decompositions into orthogonal systems (cid:24)Tim(cid:8)(cid:7)(cid:25)(cid:5) (cid:24)Wal(cid:16)(cid:13)(cid:25) like Legendre(cid:28)(cid:5) Laguerre(cid:28)(cid:5) Chebyche(cid:6)(cid:28)(cid:5) Hermite(cid:28)(cid:5) Haar(cid:28)bases and the family of Fourier Transforms(cid:5) Windowed Fourier Transforms(cid:5) Wavelets with tight frames or orthogonalsystems (cid:24)Dau(cid:16)(cid:9)(cid:25) were investigated in order to achieve e(cid:19)cient ways for true and(cid:17)or fast function approximation and data compression(cid:4) All of the approaches described above (cid:1)except approximation by nonsepara(cid:3) ble wavelet bases(cid:2) share the problem of exponentional increase in the number of coe(cid:19)cients with the dimensionality of the problem(cid:4) A solution was the way to nonseparable expansions(cid:5) e(cid:4)g(cid:4) ANOVA(cid:28)decompositions (cid:24)SHKT(cid:16)(cid:15)(cid:25)(cid:5) Neural Net(cid:3) CHAPTER (cid:6)(cid:1) A ROADMAP (cid:12) works and other methods like CART (cid:24)BFOS(cid:12)(cid:13)(cid:25)(cid:5) MARS (cid:24)Fri(cid:16)(cid:0)(cid:25) (cid:4)(cid:4)(cid:4)These methods stem fromregression estimationand allowtractable solutionsofhighdimensional problems(cid:4) Thisbringsustothecrucialquestion(cid:21) Whydoweneedanothermethod for function approximation or regression if there(cid:14)s already such a large variety of concepts available that should suit everyone(cid:14)s need(cid:29) (cid:0)(cid:1)(cid:5) The Reason for Support Vectors The reason is that allof these methods have some shortcomingswhich we tried to overcomeinthisapproach(cid:4) NeuralNetworkswhichareprobablythemostpopular way of doing high dimensional regression estimation have two drawbacks(cid:4) Their architecture has to be determined a priori or modi(cid:18)ed while training by some heuristic which results in a non necessarily optimal structure of the network and can become a di(cid:19)cult combinatorial problem for multilayer networks(cid:4) Still they are universal approximators (cid:24)Cyb(cid:12)(cid:12)(cid:25)(cid:5) (cid:24)Mur(cid:16)(cid:8)b(cid:25)(cid:4) Secondly ways of regularization (cid:1)besides the selection of the architecture(cid:2) are rather limited(cid:4) They consist of early stopping (cid:24)DH(cid:10)(cid:13)(cid:25)(cid:5) training with noise (cid:24)Bis(cid:16)(cid:15)b(cid:25)(cid:5) weight decay (cid:24)SL(cid:16)(cid:9)a(cid:25) and similar methods(cid:4) Unfortunately Neural Net(cid:3) works can get stuck in localminimawhile training(cid:4) For some methods of training (cid:1)early stopping(cid:2) it is not even desired for the network to obtain its minimum(cid:4) Hence a part of the capacity of the network is (cid:1)sometimes deliberately(cid:2) wasted in order to obtain better generalization performance(cid:4) Howewer this gives only a very indirect way of controlling the capacity of the system and is far from being optimal(cid:4) Only for the asymptotic case (cid:1)which in reality rarely occurs(cid:5) still there are some results hinting that speech recognition might be such a case(cid:2) (cid:24)MYA(cid:16)(cid:13)(cid:25)(cid:5) (cid:24)Aka(cid:10)(cid:13)(cid:25) and for the case of known prior probabilities (cid:1)which is not a realistic assumtion(cid:2) optimal selection criteria have been obtained(cid:4) Only recently good bounds on the complexity of Neural Networks have been computed by McIntyre and Karpinski (cid:24)KM(cid:16)(cid:15)(cid:25) and Hole (cid:24)Hol(cid:16)(cid:8)(cid:25)(cid:4) Still the problem of e(cid:6)ectively control(cid:3) ling the capacity after having selected the architecture remains(cid:4) Moreover after training it is rather hard to (cid:18)nd a meaningful interpretation of the weights(cid:4) CART conversely uses a purity functionalfor pruning instead of more directly motivated regularization techniques(cid:4) It also neglects the loss function speci(cid:18)c to theproblemtobesolved(cid:4) Moreoveritisquiterestrictiveintermsoftheadmissible models(cid:4) Instead it would be desirable to have a great liberty in choosing the type of functions one would like to approximate the data with and thereby adding prior knowledge to the way the approximation is constructed(cid:4) But instead of giving a de(cid:18)nition by exclusion the advantages of Support Vector Regression Estimation can be summed up easily(cid:4) The architecture of the system doesn(cid:14)t have to be determined before training(cid:4) Input data of any arbitrary dimensionality can be treated with only linear cost in the number of CHAPTER (cid:6)(cid:1) A ROADMAP (cid:16) input dimensions(cid:4) A unique solution is found after training as solution of a quadratic programing problem(cid:4) The modeling functions may be chosen among a great variety having to satisfy only some condition from Hilbert(cid:3)Schmidt theory(cid:4) Capacity can be controlled e(cid:6)ectively through the regularization functional used (cid:1)some more research willhave to be done on this point(cid:2) by the same method that was applied to Support Vector Pattern Recognition (cid:24)GBV(cid:16)(cid:11)(cid:25)(cid:4)