%0 Journal Article %1 ams:cucker %A Cucker, Felipe %A Smale, Steve %D 2002 %J Bulletin of the American Mathematical Society %K learning math theory %N 1 %T On the mathematical foundations of learning %U http://www.ams.org/mathscinet-getitem?mr=1864085 %V 39 %X In this report the authors study the relationship between approximation and learning, emphasizing the primary role of sampling (inductive inference). Tools and ideas from linear algebra, probability theory and numerical analysis (least squares algorithm) are widely used. As the authors say, "practical results are not the goal of this paper. Understanding is." With this purpose, they illustrate their statements with several examples. The main setting is the following: the existence of an ünknown" function $f\,X Y$ and a probability measure $\rho$ allowing one to randomly draw points in $X Y$ is assumed, such that for $x X$ the expected value of a randomly drawn point $y Y$ is $f(x)$. The (least squares) error of $f$ is defined by $$E(f)=ınt_X Y (f(x)-y)^2 d\rho.$$ The main goal is to find $f$ minimizing $E(f)$, where $f$ is taken from a subfamily $H$ of continuous functions with the sup-norm on $X$. Along with the optimizer $f_H$ of the problem above, the empirical target function $f_z$ is considered, minimizing the discrete least squares error for a given sample $z (X Y)^m$. Then the error $E(f_z)$ decomposes as a sum of the sample error (which measures how good $f_z$ is as an approximation of $f_H$), studied in detail in Chapter I, and the approximation error, which depends only on $H$ and $\rho$ (Chapter II). Several estimations on both errors in terms of covering numbers are provided. Also, the bias-variance trade-off problem is discussed (for larger families $H$ the approximation errors decrease, but sample errors increase, and vice-versa). Chapter III is devoted to the study of a particular choice of the families $H$, which allows the analysis of algorithms from the point of view of reproducing kernel Hilbert spaces.

@article{ams:cucker, abstract = {In this report the authors study the relationship between approximation and learning, emphasizing the primary role of sampling (inductive inference). Tools and ideas from linear algebra, probability theory and numerical analysis (least squares algorithm) are widely used. As the authors say, "practical results are not the goal of this paper. Understanding is." With this purpose, they illustrate their statements with several examples. The main setting is the following: the existence of an "unknown" function $f\colon \,X \to Y$ and a probability measure $\rho$ allowing one to randomly draw points in $X \times Y$ is assumed, such that for $x \in X$ the expected value of a randomly drawn point $y \in Y$ is $f(x)$. The (least squares) error of $f$ is defined by $$\scr E(f)=\int_{X \times Y} (f(x)-y)^2 d\rho.$$ The main goal is to find $f$ minimizing $\scr E(f)$, where $f$ is taken from a subfamily $\scr H$ of continuous functions with the sup-norm on $X$. Along with the optimizer $f_{\scr H}$ of the problem above, the empirical target function $f_{z}$ is considered, minimizing the discrete least squares error for a given sample $z \in (X \times Y)^m$. Then the error $\scr E(f_{z})$ decomposes as a sum of the sample error (which measures how good $f_z$ is as an approximation of $f_{\scr H}$), studied in detail in Chapter I, and the approximation error, which depends only on $\scr H$ and $\rho$ (Chapter II). Several estimations on both errors in terms of covering numbers are provided. Also, the bias-variance trade-off problem is discussed (for larger families $\scr H$ the approximation errors decrease, but sample errors increase, and vice-versa). Chapter III is devoted to the study of a particular choice of the families $\scr H$, which allows the analysis of algorithms from the point of view of reproducing kernel Hilbert spaces.}, added-at = {2007-04-30T12:02:22.000+0200}, author = {Cucker, Felipe and Smale, Steve}, biburl = {https://www.bibsonomy.org/bibtex/28f85b5beaa2725d11bb2a36f46644045/kzhou}, citeulike-article-id = {416041}, interhash = {0df797f759b03ac53af1f18e56911bb7}, intrahash = {8f85b5beaa2725d11bb2a36f46644045}, journal = {Bulletin of the American Mathematical Society}, keywords = {learning math theory}, number = 1, priority = {2}, timestamp = {2007-04-30T12:02:22.000+0200}, title = {On the mathematical foundations of learning}, url = {http://www.ams.org/mathscinet-getitem?mr=1864085}, volume = 39, year = 2002 }