Survey Kernel methods in system identification, machine learning and function estimation: A survey
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: A new look at the statistical model identification

paper_content:

The history of the development of statistical hypothesis testing in time series analysis is reviewed briefly and it is pointed out that the hypothesis testing procedure is not adequately defined as the procedure for statistical model identification. The classical maximum likelihood estimation procedure is reviewed and a new estimate minimum information theoretical criterion (AIC) estimate (MAICE) which is designed for the purpose of statistical identification is introduced. When there are several competing models the MAICE is defined by the model and the maximum likelihood estimates of the parameters which give the minimum of AIC defined by AIC = (-2)log-(maximum likelihood) + 2(number of independently adjusted parameters within the model). MAICE provides a versatile procedure for statistical model identification which is free from the ambiguities inherent in the application of conventional hypothesis testing procedure. The practical utility of MAICE in time series analysis is demonstrated with some numerical examples.
---
paper_title: On early stopping in gradient descent learning

paper_content:

In this paper we study a family of gradient descent algorithms to approximate the regression function from reproducing kernel Hilbert spaces (RKHSs), the family being characterized by a polynomial decreasing rate of step sizes (or learning rate). By solving a bias-variance trade-off we obtain an early stopping rule and some probabilistic upper bounds for the convergence of the algorithms. We also discuss the implication of these results in the context of classification where some fast convergence rates can be achieved for plug-in classifiers. Some connections are addressed with Boosting, Landweber iterations, and the online learning algorithms as stochastic approximations of the gradient descent method.
---
paper_title: Statistical learning theory

paper_content:

A comprehensive look at learning and generalization theory. The statistical theory of learning and generalization concerns the problem of choosing desired functions on the basis of empirical data. Highly applicable to a variety of computer science and robotics fields, this book offers lucid coverage of the theory as a whole. Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
---
paper_title: Gaussian Processes for Machine Learning

paper_content:

Gaussian processes (GPs) provide a principled, practical, probabilistic approach to learning in kernel machines. GPs have received increased attention in the machine-learning community over the past decade, and this book provides a long-needed systematic and unified treatment of theoretical and practical aspects of GPs in machine learning. The treatment is comprehensive and self-contained, targeted at researchers and students in machine learning and applied statistics.The book deals with the supervised-learning problem for both regression and classification, and includes detailed algorithms. A wide variety of covariance (kernel) functions are presented and their properties discussed. Model selection is discussed both from a Bayesian and a classical perspective. Many connections to other well-known techniques from machine learning and statistics are discussed, including support-vector machines, neural networks, splines, regularization networks, relevance vector machines and others. Theoretical issues including learning curves and the PAC-Bayesian framework are treated, and several approximation methods for learning with large datasets are discussed. The book contains illustrative examples and exercises, and code and datasets are available on the Web. Appendixes provide mathematical background and a discussion of Gaussian Markov processes.
---
paper_title: Nonparametric input estimation in physiological systems: Problems, methods, and case studies

paper_content:

Input estimation from output data is an important problem in the analysis of physiological systems, because many signals of interest are not directly accessible to measurement. When the system is time-invariant, this problem is often referred to as deconvolution. Three representative physiological problems, regarding hormone secretion, insulin dynamics, and hepatic glucose production, are used to illustrate the major challenges: ill-conditioning, confidence intervals assessment, infrequent and nonuniform sampling, nonnegativity constraints, and computational efficiency. The paper provides a critical overview of the existing techniques, focusing on regularization theory and Bayesian estimation. In order to overcome some inadequacies of the existing methods, some new results are derived. In particular, the connection between the maximum-likelihood estimate of the regularization parameter and the notion of equivalent degree of freedom is studied. Moreover, a fast SVD-based numerical algorithm is developed that includes the optimization of the regularization parameter, and the computation of confidence intervals. The proposed techniques are validated on a benchmark problem and are shown to provide effective solutions to the three physiological case studies.
---
paper_title: The minimal error conjugate gradient method is a regularization method

paper_content:

The regularizing properties of the conjugate gradient iteration, applied to the normal equation of a linear ill-posed problem, were established by Nemirovskii in 1986. A seemingly more attractive variant of this algorithm is the minimal error method suggested by King. The present paper analyzes the regularizing properties of the minimal error method. It is shown that the discrepancy principle is no regularizing stopping rule for the minimal error method. Instead, a different stopping rule is suggested which leads to order-optimal convergence rates.
---
paper_title: Prediction error identification of linear systems: A nonparametric Gaussian regression approach

paper_content:

A novel Bayesian paradigm for the identification of output error models has recently been proposed in which, in place of postulating finite-dimensional models of the system transfer function, the system impulse response is searched for within an infinite-dimensional space. In this paper, such a nonparametric approach is applied to the design of optimal predictors and discrete-time models based on prediction error minimization by interpreting the predictor impulse responses as realizations of Gaussian processes. The proposed scheme describes the predictor impulse responses as the convolution of an infinite-dimensional response with a low-dimensional parametric response that captures possible high-frequency dynamics. Overparameterization is avoided because the model involves only a few hyperparameters that are tuned via marginal likelihood maximization. Numerical experiments, with data generated by ARMAX and infinite-dimensional models, show the definite advantages of the new approach over standard parametric prediction error techniques and subspace methods both in terms of predictive capability on new data and accuracy in reconstruction of system impulse responses.
---
paper_title: System Identification: Theory for the User

paper_content:

Das Buch behandelt die Systemidentifizierung in dem theoretischen Bereich, der direkte Auswirkungen auf Verstaendnis und praktische Anwendung der verschiedenen Verfahren zur Identifizierung hat. Da ...
---
paper_title: On the mathematical foundations of learning

paper_content:

(1) A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference). We try to emphasize relations of the theory of learning to the mainstream of mathematics. In particular, there are large roles for probability theory, for algorithms such as least squares, and for tools and ideas from linear algebra and linear analysis. An advantage of doing this is that communication is facilitated and the power of core mathematics is more easily brought to bear. We illustrate what we mean by learning theory by giving some instances. (a) The understanding of language acquisition by children or the emergence of languages in early human cultures. (b) In Manufacturing Engineering, the design of a new wave of machines is anticipated which uses sensors to sample properties of objects before, during, and after treatment. The information gathered from these samples is to be analyzed by the machine to decide how to better deal with new input objects (see [43]). (c) Pattern recognition of objects ranging from handwritten letters of the alphabet to pictures of animals, to the human voice. Understanding the laws of learning plays a large role in disciplines such as (Cognitive) Psychology, Animal Behavior, Economic Decision Making, all branches of Engineering, Computer Science, and especially the study of human thought processes (how the brain works). Mathematics has already played a big role towards the goal of giving a universal foundation of studies in these disciplines. We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments. We are heavily indebted to these developments. Recent discussions with a number of mathematicians have also been helpful. In
---
paper_title: On the estimation of transfer functions , regularizations and Gaussian processes-Revisited

paper_content:

Intrigued by some recent results on impulse response estimation by kernel and nonparametric techniques, we revisit the old problem of transfer function estimation from input-output measurements. We formulate a classical regularization approach, focused on finite impulse response (FIR) models, and find that regularization is necessary to cope with the high variance problem. This basic, regularized least squares approach is then a focal point for interpreting other techniques, like Bayesian inference and Gaussian process regression. The main issue is how to determine a suitable regularization matrix (Bayesian prior or kernel). Several regularization matrices are provided and numerically evaluated on a data bank of test systems and data sets. Our findings based on the data bank are as follows. The classical regularization approach with carefully chosen regularization matrices shows slightly better accuracy and clearly better robustness in estimating the impulse response than the standard approach-the prediction error method/maximum likelihood (PEM/ML) approach. If the goal is to estimate a model of given order as well as possible, a low order model is often better estimated by the PEM/ML approach, and a higher order model is often better estimated by model reduction on a high order regularized FIR model estimated with careful regularization. Moreover, an optimal regularization matrix that minimizes the mean square error matrix is derived and studied. The importance of this result lies in that it gives the theoretical upper bound on the accuracy that can be achieved for this classical regularization approach.
---
paper_title: Inverse Problem Theory and Methods for Model Parameter Estimation

paper_content:

1. The general discrete inverse problem 2. Monte Carol methods 3. The least-squares criterion 4. Least-absolute values criterion and minimax criterion 5. Functional inverse problems 6. Appendices 7. Problems References Index.
---
paper_title: The truncated SVD as a method for regularization

paper_content:

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in case of ill-conditioned matrices with a well-determined rank.
---
paper_title: Theory of reproducing kernels

paper_content:

Abstract : The present paper may be considered as a sequel to our previous paper in the Proceedings of the Cambridge Philosophical Society, Theorie generale de noyaux reproduisants-Premiere partie (vol. 39 (1944)) which was written in 1942-1943. In the introduction to this paper we outlined the plan of papers which were to follow. In the meantime, however, the general theory has been developed in many directions, and our original plans have had to be changed. Due to wartime conditions we were not able, at the time of writing the first paper, to take into account all the earlier investigations which, although sometimes of quite a different character, were, nevertheless, related to our subject. Our investigation is concerned with kernels of a special type which have been used under different names and in different ways in many domains of mathematical research. We shall therefore begin our present paper with a short historical introduction in which we shall attempt to indicate the different manners in which these kernels have been used by various investigators, and to clarify the terminology. We shall also discuss the more important trends of the application of these kernels without attempting, however, a complete bibliography of the subject matter. (KAR) P. 2
---
paper_title: A Generalized Representer Theorem

paper_content:

Wahba's classical representer theorem states that the solutions of certain risk minimization problems involving an empirical risk term and a quadratic regularizer can be written as expansions in terms of the training examples. We generalize the theorem to a larger class of regularizers and empirical risk terms, and give a self-contained proof utilizing the feature space associated with a kernel. The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.
---
paper_title: System Identification: A Frequency Domain Approach

paper_content:

System identification is a general term used to describe mathematical tools and algorithms that build dynamical models from measured data. Used for prediction, control, physical interpretation, and the designing of any electrical systems, they are vital in the fields of electrical, mechanical, civil, and chemical engineering. Focusing mainly on frequency domain techniques, System Identification: A Frequency Domain Approach, Second Edition also studies in detail the similarities and differences with the classical time domain approach. It high??lights many of the important steps in the identification process, points out the possible pitfalls to the reader, and illustrates the powerful tools that are available.
---
paper_title: System Identification: Theory for the User

paper_content:

Das Buch behandelt die Systemidentifizierung in dem theoretischen Bereich, der direkte Auswirkungen auf Verstaendnis und praktische Anwendung der verschiedenen Verfahren zur Identifizierung hat. Da ...
---
paper_title: Black-box identification of MIMO transfer functions : asymptotic properties of prediction error models

paper_content:

Identification of multi-input/multi-output (MIMO) transfer functions is considered. The transfer function matrix is parametrized as black-box models which have certain shift properties; no structure or order is chosen a priori. In order to obtain a good transfer function estimate, we allow the order of the model to increase to infinity as the number of data tends to infinity. The expression of asymptotic covariance of the transfer function estimates is derived, which is asymptotic both in the number of data and in the model order. The result indicates that the joint covariance matrix of the transfer function estimates of the process and of the noise filter is proportional to the (generalized) ratio of output noise to imput signal; the factor of proportionality is the ratio of model order to number of data. The result is independent of the particular model structure used. This result is the MIMO extension of the theory of Ljung. The application of this theory for defining the upper bounds of identification errors is highlighted.
---
paper_title: Identification of Multivariable Industrial Processes for Simulation, Diagnosis and Control

paper_content:

Linear Models of Dynamic Processes and Signals.-Identification Experiment and Data Pre-Treatment.-Identification by the Least Squares Method.- Extensions of the Least-Squares Method.- MIMO Process Identification: A Markov Parameter Approach.- Identification for Robust Control SISO Case.- Identification for Robust Control MIMO Case.-Identification and Robust Control of the Glass Tube Process.-Identification for Fault Diagnosis Estimation of Continuous-Time Models.
---
paper_title: System Identification: Theory for the User

paper_content:

Das Buch behandelt die Systemidentifizierung in dem theoretischen Bereich, der direkte Auswirkungen auf Verstaendnis und praktische Anwendung der verschiedenen Verfahren zur Identifizierung hat. Da ...
---
paper_title: A new look at the statistical model identification

paper_content:

The history of the development of statistical hypothesis testing in time series analysis is reviewed briefly and it is pointed out that the hypothesis testing procedure is not adequately defined as the procedure for statistical model identification. The classical maximum likelihood estimation procedure is reviewed and a new estimate minimum information theoretical criterion (AIC) estimate (MAICE) which is designed for the purpose of statistical identification is introduced. When there are several competing models the MAICE is defined by the model and the maximum likelihood estimates of the parameters which give the minimum of AIC defined by AIC = (-2)log-(maximum likelihood) + 2(number of independently adjusted parameters within the model). MAICE provides a versatile procedure for statistical model identification which is free from the ambiguities inherent in the application of conventional hypothesis testing procedure. The practical utility of MAICE in time series analysis is demonstrated with some numerical examples.
---
paper_title: Modeling by shortest data description

paper_content:

The number of digits it takes to write down an observed sequence x"1, ..., x"N of a time series depends on the model with its parameters that one assumes to have generated the observed data. Accordingly, by finding the model which minimizes the description length one obtains estimates of both the integer-valued structure parameters and the real-valued system parameters.
---
paper_title: Regression and time series model selection in small samples

paper_content:

SUMMARY A bias correction to the Akaike information criterion, AIC, is derived for regression and autoregressive time series models. The correction is of particular use when the sample size is small, or when the number of fitted parameters is a moderate to large fraction of the sample size. The corrected method, called AICC, is asymptotically efficient if the true model is infinite dimensional. Furthermore, when the true model is of finite dimension, AICC is found to provide better model order choices than any other asymptotically efficient method. Applications to nonstationary autoregressive and mixed autoregressive moving average time series models are also discussed.
---
paper_title: On the estimation of transfer functions , regularizations and Gaussian processes-Revisited

paper_content:

Intrigued by some recent results on impulse response estimation by kernel and nonparametric techniques, we revisit the old problem of transfer function estimation from input-output measurements. We formulate a classical regularization approach, focused on finite impulse response (FIR) models, and find that regularization is necessary to cope with the high variance problem. This basic, regularized least squares approach is then a focal point for interpreting other techniques, like Bayesian inference and Gaussian process regression. The main issue is how to determine a suitable regularization matrix (Bayesian prior or kernel). Several regularization matrices are provided and numerically evaluated on a data bank of test systems and data sets. Our findings based on the data bank are as follows. The classical regularization approach with carefully chosen regularization matrices shows slightly better accuracy and clearly better robustness in estimating the impulse response than the standard approach-the prediction error method/maximum likelihood (PEM/ML) approach. If the goal is to estimate a model of given order as well as possible, a low order model is often better estimated by the PEM/ML approach, and a higher order model is often better estimated by model reduction on a high order regularized FIR model estimated with careful regularization. Moreover, an optimal regularization matrix that minimizes the mean square error matrix is derived and studied. The importance of this result lies in that it gives the theoretical upper bound on the accuracy that can be achieved for this classical regularization approach.
---
paper_title: Quantifying the Error in Estimated Transfer Functions with Application to Model Order Selection

paper_content:

Previous results on estimating errors or error bounds on identified transfer functions have relied upon prior assumptions about the noise and the unmodeled dynamics. This prior information took the form of parameterized bounding functions or parameterized probability density functions, in the time or frequency domain with known parameters. Here we show that the parameters that quantify this prior information can themselves be estimated from the data using a maximum likelihood technique. This significantly reduces the prior infor- mation required to estimate transfer function error bounds. We illustrate the usefulness of the method with a number of simula- tion examples. The paper concludes by showing how the obtained error bounds can be used for intelligent model order selection that takes into account both measurement noise and under-model- ing. Another simulation study compares our method to Akaike's well-known FPE and AIC criteria.
---
paper_title: System Identification: Theory for the User

paper_content:

Das Buch behandelt die Systemidentifizierung in dem theoretischen Bereich, der direkte Auswirkungen auf Verstaendnis und praktische Anwendung der verschiedenen Verfahren zur Identifizierung hat. Da ...
---
paper_title: System Identification Via Sparse Multiple Kernel-Based Regularization Using Sequential Convex Optimization Techniques

paper_content:

Model estimation and structure detection with short data records are two issues that receive increasing interests in System Identification. In this paper, a multiple kernel-based regularization method is proposed to handle those issues. Multiple kernels are conic combinations of fixed kernels suitable for impulse response estimation, and equip the kernel-based regularization method with three features. First, multiple kernels can better capture complicated dynamics than single kernels. Second, the estimation of their weights by maximizing the marginal likelihood favors sparse optimal weights, which enables this method to tackle various structure detection problems, e.g., the sparse dynamic network identification and the segmentation of linear systems. Third, the marginal likelihood maximization problem is a difference of convex programming problem. It is thus possible to find a locally optimal solution efficiently by using a majorization minimization algorithm and an interior point method where the cost of a single interior-point iteration grows linearly in the number of fixed kernels. Monte Carlo simulations show that the locally optimal solutions lead to good performance for randomly generated starting points.
---
paper_title: Kernel selection in linear system identification part II: A classical perspective

paper_content:

In this companion paper, the choice of kernels for estimating the impulse response of linear stable systems is considered from a classical, “frequentist”, point of view. The kernel determines the regularization matrix in a regularized least squares estimate of an FIR model. The quality is assessed from a mean square error (MSE) perspective, and measures and algorithms for optimizing the MSE are discussed. The ideas are tested on the same data bank as used in Part I of the companion papers. The resulting findings and conclusions in the two papers are very similar despite the different perspectives.
---
paper_title: On the estimation of transfer functions , regularizations and Gaussian processes-Revisited

paper_content:

Intrigued by some recent results on impulse response estimation by kernel and nonparametric techniques, we revisit the old problem of transfer function estimation from input-output measurements. We formulate a classical regularization approach, focused on finite impulse response (FIR) models, and find that regularization is necessary to cope with the high variance problem. This basic, regularized least squares approach is then a focal point for interpreting other techniques, like Bayesian inference and Gaussian process regression. The main issue is how to determine a suitable regularization matrix (Bayesian prior or kernel). Several regularization matrices are provided and numerically evaluated on a data bank of test systems and data sets. Our findings based on the data bank are as follows. The classical regularization approach with carefully chosen regularization matrices shows slightly better accuracy and clearly better robustness in estimating the impulse response than the standard approach-the prediction error method/maximum likelihood (PEM/ML) approach. If the goal is to estimate a model of given order as well as possible, a low order model is often better estimated by the PEM/ML approach, and a higher order model is often better estimated by model reduction on a high order regularized FIR model estimated with careful regularization. Moreover, an optimal regularization matrix that minimizes the mean square error matrix is derived and studied. The importance of this result lies in that it gives the theoretical upper bound on the accuracy that can be achieved for this classical regularization approach.
---
paper_title: Convex analysis approach to d.c. programming: Theory, Algorithm and Applications

paper_content:

Dedicated to Hoang Tuy on the occasion of his seventieth birthday Abstract. This paper is devoted to a thorough study on convex analysis approach to d.c. (difierence of convex functions) programming and gives the State of the Art. Main results about d.c. duality, local and global opti- malities in d.c. programming are presented. These materials constitute the basis of the DCA (d.c. algorithms). Its convergence properties have been tackled in detail, especially in d.c. polyhedral programming where it has flnite convergence. Exact penalty, Lagrangian duality without gap, and regularization techniques have beeen studied to flnd appropriate d.c. de- compositions and to improve consequently the DCA. Finally we present the application of the DCA to solving a lot of important real-life d.c. pro- grams.
---
paper_title: DC Programming: Overview

paper_content:

Mathematical programming problems dealing with functions, each of which can be represented as a difference of two convex functions, are called DC programming problems. The purpose of this overview is to discuss main theoretical results, some applications, and solution methods for this interesting and important class of programming problems. Some modifications and new results on the optimality conditions and development of algorithms are also presented.
---
paper_title: System Identification Via Sparse Multiple Kernel-Based Regularization Using Sequential Convex Optimization Techniques

paper_content:

Model estimation and structure detection with short data records are two issues that receive increasing interests in System Identification. In this paper, a multiple kernel-based regularization method is proposed to handle those issues. Multiple kernels are conic combinations of fixed kernels suitable for impulse response estimation, and equip the kernel-based regularization method with three features. First, multiple kernels can better capture complicated dynamics than single kernels. Second, the estimation of their weights by maximizing the marginal likelihood favors sparse optimal weights, which enables this method to tackle various structure detection problems, e.g., the sparse dynamic network identification and the segmentation of linear systems. Third, the marginal likelihood maximization problem is a difference of convex programming problem. It is thus possible to find a locally optimal solution efficiently by using a majorization minimization algorithm and an interior point method where the cost of a single interior-point iteration grows linearly in the number of fixed kernels. Monte Carlo simulations show that the locally optimal solutions lead to good performance for randomly generated starting points.
---
paper_title: Estimation with Quadratic Loss

paper_content:

It has long been customary to measure the adequacy of an estimator by the smallness of its mean squared error. The least squares estimators were studied by Gauss and by other authors later in the nineteenth century. A proof that the best unbiased estimator of a linear function of the means of a set of observed random variables is the least squares estimator was given by Markov [12], a modified version of whose proof is given by David and Neyman [4]. A slightly more general theorem is given by Aitken [1]. Fisher [5] indicated that for large samples the maximum likelihood estimator approximately minimizes the mean squared error when compared with other reasonable estimators. This paper will be concerned with optimum properties or failure of optimum properties of the natural estimator in certain special problems with the risk usually measured by the mean squared error or, in the case of several parameters, by a quadratic function of the estimators. We shall first mention some recent papers on this subject and then give some results, mostly unpublished, in greater detail.
---
paper_title: Stein's Estimation Rule and Its Competitors- An Empirical Bayes Approach

paper_content:

Abstract Stein's estimator for k normal means is known to dominate the MLE if k ≥ 3. In this article we ask if Stein's estimator is any good in its own right. Our answer is yes: the positive part version of Stein's estimator is one member of a class of “good” rules that have Bayesian properties and also dominate the MLE. Other members of this class are also useful in various situations. Our approach is by means of empirical Bayes ideas. In the later sections we discuss rules for more complicated estimation problems, and conclude with results from empirical linear Bayes rules in non-normal cases.
---
paper_title: Minimax Adaptive Generalized Ridge Regression Estimators

paper_content:

Abstract We consider the problem of estimating the vector of regression coefficients of a linear model using generalized ridge regression estimators where the ridge constant is chosen on the basis of the data. For general quadratic loss we produce such estimators whose risk function dominates that of the least squares procedure provided the number of regressors is at least three. We study the problem by the usual reduction to estimating the mean vector of a multivariate normal distribution. Our results on minimax estimation in this context are of independent interest.
---
paper_title: Minimax Ridge Regression Estimation

paper_content:

Abstract : The technique of ridge regression has become a popular tool for data analysts faced with a high degree of multicollinearity in their data. By using a ridge estimator, it was hoped that one could both stabilize the estimates (lower the condition number of the design matrix) and improve upon the squared error loss of the least squares estimator. Recently classes of ridge regression estimators have been developed which dominate the usual estimator in risk, and hence are minimax. This paper derives conditions that are necessary and sufficient for minimaxity of a large class of ridge regression estimators. The conditions derived here are very similar to those derived for minimaxity of some Stein-type estimators.
---
paper_title: Quantifying the Error in Estimated Transfer Functions with Application to Model Order Selection

paper_content:

Previous results on estimating errors or error bounds on identified transfer functions have relied upon prior assumptions about the noise and the unmodeled dynamics. This prior information took the form of parameterized bounding functions or parameterized probability density functions, in the time or frequency domain with known parameters. Here we show that the parameters that quantify this prior information can themselves be estimated from the data using a maximum likelihood technique. This significantly reduces the prior infor- mation required to estimate transfer function error bounds. We illustrate the usefulness of the method with a number of simula- tion examples. The paper concludes by showing how the obtained error bounds can be used for intelligent model order selection that takes into account both measurement noise and under-model- ing. Another simulation study compares our method to Akaike's well-known FPE and AIC criteria.
---
paper_title: Extended benchmark results for impulse response estimation

paper_content:

Recent attention has been given to the use of regularised least-squares methods for improving the quality of classical impulse response estimates from short/noisy datasets. This paper significantly augments and contextualises previously reported benchmark results by inclusion of a larger set of standard and non-standard methods in the comparison. The numerical experiments are summarised using several metrics. There is no obvious winner method.
---
paper_title: On the mathematical foundations of learning

paper_content:

(1) A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference). We try to emphasize relations of the theory of learning to the mainstream of mathematics. In particular, there are large roles for probability theory, for algorithms such as least squares, and for tools and ideas from linear algebra and linear analysis. An advantage of doing this is that communication is facilitated and the power of core mathematics is more easily brought to bear. We illustrate what we mean by learning theory by giving some instances. (a) The understanding of language acquisition by children or the emergence of languages in early human cultures. (b) In Manufacturing Engineering, the design of a new wave of machines is anticipated which uses sensors to sample properties of objects before, during, and after treatment. The information gathered from these samples is to be analyzed by the machine to decide how to better deal with new input objects (see [43]). (c) Pattern recognition of objects ranging from handwritten letters of the alphabet to pictures of animals, to the human voice. Understanding the laws of learning plays a large role in disciplines such as (Cognitive) Psychology, Animal Behavior, Economic Decision Making, all branches of Engineering, Computer Science, and especially the study of human thought processes (how the brain works). Mathematics has already played a big role towards the goal of giving a universal foundation of studies in these disciplines. We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments. We are heavily indebted to these developments. Recent discussions with a number of mathematicians have also been helpful. In
---
paper_title: Theory of reproducing kernels

paper_content:

Abstract : The present paper may be considered as a sequel to our previous paper in the Proceedings of the Cambridge Philosophical Society, Theorie generale de noyaux reproduisants-Premiere partie (vol. 39 (1944)) which was written in 1942-1943. In the introduction to this paper we outlined the plan of papers which were to follow. In the meantime, however, the general theory has been developed in many directions, and our original plans have had to be changed. Due to wartime conditions we were not able, at the time of writing the first paper, to take into account all the earlier investigations which, although sometimes of quite a different character, were, nevertheless, related to our subject. Our investigation is concerned with kernels of a special type which have been used under different names and in different ways in many domains of mathematical research. We shall therefore begin our present paper with a short historical introduction in which we shall attempt to indicate the different manners in which these kernels have been used by various investigators, and to clarify the terminology. We shall also discuss the more important trends of the application of these kernels without attempting, however, a complete bibliography of the subject matter. (KAR) P. 2
---
paper_title: Some results on Tchebycheffian spline functions

paper_content:

Abstract This report derives explicit solutions to problems involving Tchebycheffian spline functions. We use a reproducing kernel Hilbert space which depends on the smoothness criterion, but not on the form of the data, to solve explicitly Hermite-Birkhoff interpolation and smoothing problems. Sard's best approximation to linear functionals and smoothing with respect to linear inequality constraints are also discussed. Some of the results are used to show that spline interpolation and smoothing is equivalent to prediction and filtering on realizations of certain stochastic processes.
---
paper_title: Networks for approximation and learning

paper_content:

The problem of the approximation of nonlinear mapping, (especially continuous mappings) is considered. Regularization theory and a theoretical framework for approximation (based on regularization techniques) that leads to a class of three-layer networks called regularization networks are discussed. Regularization networks are mathematically related to the radial basis functions, mainly used for strict interpolation tasks. Learning as approximation and learning as hypersurface reconstruction are discussed. Two extensions of the regularization approach are presented, along with the approach's corrections to splines, regularization, Bayes formulation, and clustering. The theory of regularization networks is generalized to a formulation that includes task-dependent clustering and dimensionality reduction. Applications of regularization networks are discussed. >
---
paper_title: Learning rates of least-square regularized regression

paper_content:

This paper considers the regularized learning algorithm associated with the least-square loss and reproducing kernel Hilbert spaces. The target is the error analysis for the regression problem in learning theory. A novel regularization approach is presented, which yields satisfactory learning rates. The rates depend on the approximation property and on the capacity of the reproducing kernel Hilbert space measured by covering numbers. When the kernel is C∞ and the regression function lies in the corresponding reproducing kernel Hilbert space, the rate is mζ with ζ arbitrarily close to 1, regardless of the variance of the bounded probability distribution.
---
paper_title: Consistent identification of NARX models via regularization networks

paper_content:

Generalization networks are nonparametric estimators obtained from the application of Tychonov regularization or Bayes estimation to the hypersurface reconstruction problem. Under symmetry assumptions, they are a particular type of radial basis function neural network. In this correspondence, it is shown that such networks guarantee consistent identification of a very general (infinite-dimensional) class of NARX models. The proofs are based on the theory of reproducing kernel Hilbert spaces and the notion of frequency of time probability, by means of which it is not necessary to assume that the input is sampled from a stochastic process.
---
paper_title: Statistical learning theory

paper_content:

A comprehensive look at learning and generalization theory. The statistical theory of learning and generalization concerns the problem of choosing desired functions on the basis of empirical data. Highly applicable to a variety of computer science and robotics fields, this book offers lucid coverage of the theory as a whole. Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: Kernel methods in machine learning

paper_content:

We review machine learning methods employing positive definite kernels. These methods formulate learning and estimation problems in a reproducing kernel Hilbert space (RKHS) of functions defined on the data domain, expanded in terms of a kernel. Working in linear spaces of function has the benefit of facilitating the construction and analysis of learning algorithms while at the same time allowing large classes of functions. The latter include nonlinear functions as well as functions defined on nonvectorial data. We cover a wide range of methods, ranging from binary classifiers to sophisticated methods for estimation with structured data.
---
paper_title: Kernel Methods for Pattern Analysis

paper_content:

Kernel methods provide a powerful and unified framework for pattern discovery, motivating algorithms that can act on general types of data (e.g. strings, vectors or text) and look for general types of relations (e.g. rankings, classifications, regressions, clusters). The application areas range from neural networks and pattern recognition to machine learning and data mining. This book, developed from lectures and tutorials, fulfils two major roles: firstly it provides practitioners with a large toolkit of algorithms, kernels and solutions ready to use for standard pattern discovery problems in fields such as bioinformatics, text analysis, image analysis. Secondly it provides an easy introduction for students and researchers to the growing field of kernel-based pattern analysis, demonstrating with examples how to handcraft an algorithm or a kernel for a new specific application, and covering all the necessary conceptual and mathematical tools to do so.
---
paper_title: On the influence of the kernel on the consistency of support vector machines

paper_content:

In this article we study the generalization abilities of several classifiers of support vector machine (SVM) type using a certain class of kernels that we call universal. It is shown that the soft margin algorithms with universal kernels are consistent for a large class of classification problems including some kind of noisy tasks provided that the regularization parameter is chosen well. In particular we derive a simple sufficient condition for this parameter in the case of Gaussian RBF kernels. On the one hand our considerations are based on an investigation of an approximation property---the so-called universality---of the used kernels that ensures that all continuous functions can be approximated by certain kernel expressions. This approximation property also gives a new insight into the role of kernels in these and other algorithms. On the other hand the results are achieved by a precise study of the underlying optimization problems of the classifiers. Furthermore, we show consistency for the maximal margin classifier as well as for the soft margin SVM's in the presence of large margins. In this case it turns out that also constant regularization parameters ensure consistency for the soft margin SVM's. Finally we prove that even for simple, noise free classification problems SVM's with polynomial kernels can behave arbitrarily badly.
---
paper_title: An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels

paper_content:

Although Gaussian radial basis function (RBF) kernels are one of the most often used kernels in modern machine learning methods such as support vector machines (SVMs), little is known about the structure of their reproducing kernel Hilbert spaces (RKHSs). In this work, two distinct explicit descriptions of the RKHSs corresponding to Gaussian RBF kernels are given and some consequences are discussed. Furthermore, an orthonormal basis for these spaces is presented. Finally, it is discussed how the results can be used for analyzing the learning performance of SVMs
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: Bayesian semiparametric Wiener system identification

paper_content:

We present a novel method for Wiener system identication. The method relies on a semiparametric, i.e. a mixed parametric/nonparametric, model of a Wiener system. We use a state-space model for the linear dynamical system and a nonparametric Gaussian process model for the static nonlinearity. We avoid making strong assumptions, such as monotonicity, on the nonlinear mapping. Stochastic disturbances, entering both as measurement noise and as process noise, are handled in a systematic manner. The nonparametric nature of the Gaussian process allows us to handle a wide range of nonlinearities without making problem-specic parameterizations. We also consider sparsity-promoting priors, based on generalized hyperbolic distributions, to automatically infer the order of the underlying dynamical system. We derive an inference algorithm based on an ecient particle Markov chain Monte Carlo method, referred to as particle Gibbs with ancestor sampling. The method is proled on two challenging identication problems with good results. Blind Wiener system identication is handled as a special case.
---
paper_title: Least squares support vector machine based partially linear model identification

paper_content:

A nonlinear identification method was proposed for a class of partially linear models (PLM) which consist of a linear component summed with a nonlinear component in nonlinear ARX form. The method extends the standard least squares support vector machine (LSSVM) by replacing the equality constraint in the standard LSSVM with a PLM model. To guarantee the uniqueness of the linear coefficients, we imposed an additional explicit constraint on the feature map instead of an implicit constraint on the regressor vectors. Therefore the resulting PLM is a generalized version of the original one. Two examples show the effectiveness of the presented method.
---
paper_title: Kernel based partially linear models and nonlinear identification

paper_content:

In this note, we propose partially linear models with least squares support vector machines (LS-SVMs) for nonlinear ARX models. We illustrate how full black-box models can be improved when prior information about model structure is available. A real-life example, based on the Silverbox benchmark data, shows significant improvements in the generalization ability of the structured model with respect to the full black-box model, reflected also by a reduction in the effective number of parameters.
---
paper_title: A Unifying View of Wiener and Volterra Theory and Polynomial Kernel Regression

paper_content:

Volterra and Wiener series are perhaps the best-understood nonlinear system representations in signal processing. Although both approaches have enjoyed a certain popularity in the past, their application has been limited to rather low-dimensional and weakly nonlinear systems due to the exponential growth of the number of terms that have to be estimated. We show that Volterra and Wiener series can be represented implicitly as elements of a reproducing kernel Hilbert space by using polynomial kernels. The estimation complexity of the implicit representation is linear in the input dimensionality and independent of the degree of nonlinearity. Experiments show performance advantages in terms of convergence, interpretability, and system sizes that can be handled.
---
paper_title: Partially-Linear Least-Squares Regularized Regression for System Identification

paper_content:

In this technical note, we propose a partially-linear least-squares regularized regression (PL-LSRR) method for system identification. This method identifies a general nonlinear function as a sum of two functions which come from a linear and a nonlinear function space respectively. Both the linear and nonlinear functions can involve all regressors. Therefore, the PL-LSRR can make use of the partially-linear structure of a given system to reduce prediction errors more efficiently than exiting partially-linear identification methods. Two examples show that the PL-LSRR can reduce prediction errors and estimate the true linear expansion of the system well.
---
paper_title: Least-Squares Support Vector Machines for the identification of Wiener–Hammerstein systems

paper_content:

This paper considers the identification of Wiener-Hammerstein systems using Least-Squares Support Vector Machines based models. The power of fully black-box NARX-type models is evaluated and compar ...
---
paper_title: Modelling and control of nonlinear systems using Gaussian processes with partial model information

paper_content:

Gaussian processes are gaining increasing popularity among the control community, in particular for the modelling of discrete time state space systems. However, it has not been clear how to incorporate model information, in the form of known state relationships, when using a Gaussian process as a predictive model. An obvious example of known prior information is position and velocity related states. Incorporation of such information would be beneficial both computationally and for faster dynamics learning. This paper introduces a method of achieving this, yielding faster dynamics learning and a reduction in computational effort from O(Dn2) to O((D − F)n2) in the prediction stage for a system with D states, F known state relationships and n observations. The effectiveness of the method is demonstrated through its inclusion in the PILCO learning algorithm with application to the swing-up and balance of a torque-limited pendulum and the balancing of a robotic unicycle in simulation.
---
paper_title: Identification of MIMO Hammerstein models using least squares support vector machines

paper_content:

This paper studies a method for the identification of Hammerstein models based on least squares support vector machines (LS-SVMs). The technique allows for the determination of the memoryless static nonlinearity as well as the estimation of the model parameters of the dynamic ARX part. This is done by applying the equivalent of Bai's overparameterization method for identification of Hammerstein systems in an LS-SVM context. The SISO as well as the MIMO identification cases are elaborated. The technique can lead to significant improvements with respect to classical overparameterization methods as illustrated in a number of examples. Another important advantage is that no stringent assumptions on the nature of the nonlinearity need to be imposed except for a certain degree of smoothness.
---
paper_title: A New Kernel-Based Approach for NonlinearSystem Identification

paper_content:

We present a novel nonparametric approach for identification of nonlinear systems. Exploiting the framework of Gaussian regression, the unknown nonlinear system is seen as a realization from a Gaussian random field. Its covariance encodes the idea of “fading” memory in the predictor and consists of a mixture of Gaussian kernels parametrized by few hyperparameters describing the interactions among past inputs and outputs. The kernel structure and the unknown hyperparameters are estimated maximizing their marginal likelihood so that the user is not required to define any part of the algorithmic architecture, e.g., the regressors and the model order. Once the kernel is estimated, the nonlinear model is obtained solving a Tikhonov-type variational problem. The Hilbert space the estimator belongs to is characterized. Benchmarks problems taken from the literature show the effectiveness of the new approach, also comparing its performance with a recently proposed algorithm based on direct weight optimization and with parametric approaches with model order estimated by AIC or BIC.
---
paper_title: Identification of Wiener-Hammerstein Systems using LS-SVMs

paper_content:

Abstract This paper extends the overparametrization technique as used for Hammerstein systems employing nonlinear Least-Squares Support Vector Machines (LS-SVMs) towards the identification of Wiener-Hammerstein systems. We present some practical guidelines as well as empirical results on the performance of the method with respect to various deficiencies of the excitation signal. Finally we apply our method to the SYSID2009 Wiener-Hammerstein benchmark data set.
---
paper_title: Bayesian Inference and Learning in Gaussian Process State-Space Models with Particle MCMC

paper_content:

State-space models are successfully used in many areas of science, engineering and economics to model time series and dynamical systems. We present a fully Bayesian approach to inference and learning (i.e. state estimation and system identification) in nonlinear nonparametric state-space models. We place a Gaussian process prior over the state transition dynamics, resulting in a flexible model able to capture complex dynamical phenomena. To enable efficient inference, we marginalize over the transition dynamics function and, instead, infer directly the joint smoothing distribution using specially tailored Particle Markov Chain Monte Carlo samplers. Once a sample from the smoothing distribution is computed, the state transition predictive distribution can be formulated analytically. Our approach preserves the full nonparametric expressivity of the model and can make use of sparse Gaussian processes to greatly reduce computational complexity.
---
paper_title: A spectral characterization of the ill-conditioning in numerical deconvolution

paper_content:

An important class of applications in digital signal processing involves the numerical solution of the convolution integral. These so-called numerical deconvolution problems are notoriously difficult to solve because of their inherent ill-conditioning. In this paper we present a characterization of this ill-conditioning based on a classical spectral decomposition of the discrete convolution. Factors prominently influencing the conditioning are identified and some explicit sensitivity measures are introduced.
---
paper_title: Learning from examples as an inverse problem

paper_content:

Many works related learning from examples to regularization techniques for inverse problems, emphasizing the strong algorithmic and conceptual analogy of certain learning algorithms with regularization algorithms. In particular it is well known that regularization schemes such as Tikhonov regularization can be effectively used in the context of learning and are closely related to algorithms such as support vector machines. Nevertheless the connection with inverse problem was considered only for the discrete (finite sample) problem and the probabilistic aspects of learning from examples were not taken into account. In this paper we provide a natural extension of such analysis to the continuous (population) case and study the interplay between the discrete and continuous problems. From a theoretical point of view, this allows to draw a clear connection between the consistency approach in learning theory and the stability convergence property in ill-posed inverse problems. The main mathematical result of the paper is a new probabilistic bound for the regularized least-squares algorithm. By means of standard results on the approximation term, the consistency of the algorithm easily follows.
---
paper_title: System Identification: Theory for the User

paper_content:

Das Buch behandelt die Systemidentifizierung in dem theoretischen Bereich, der direkte Auswirkungen auf Verstaendnis und praktische Anwendung der verschiedenen Verfahren zur Identifizierung hat. Da ...
---
paper_title: Theory of reproducing kernels

paper_content:

Abstract : The present paper may be considered as a sequel to our previous paper in the Proceedings of the Cambridge Philosophical Society, Theorie generale de noyaux reproduisants-Premiere partie (vol. 39 (1944)) which was written in 1942-1943. In the introduction to this paper we outlined the plan of papers which were to follow. In the meantime, however, the general theory has been developed in many directions, and our original plans have had to be changed. Due to wartime conditions we were not able, at the time of writing the first paper, to take into account all the earlier investigations which, although sometimes of quite a different character, were, nevertheless, related to our subject. Our investigation is concerned with kernels of a special type which have been used under different names and in different ways in many domains of mathematical research. We shall therefore begin our present paper with a short historical introduction in which we shall attempt to indicate the different manners in which these kernels have been used by various investigators, and to clarify the terminology. We shall also discuss the more important trends of the application of these kernels without attempting, however, a complete bibliography of the subject matter. (KAR) P. 2
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: A reproducing kernel Hilbert space approach to functional linear regression

paper_content:

We study in this paper a smoothness regularization method for functional linear regression and provide a unified treatment for both the prediction and estimation problems. By developing a tool on simultaneous diagonalization of two positive definite kernels, we obtain shaper results on the minimax rates of convergence and show that smoothness regularized estimators achieve the optimal rates of convergence for both prediction and estimation under conditions weaker than those for the functional principal components based methods developed in the literature. Despite the generality of the method of regularization, we show that the procedure is easily implementable. Numerical results are obtained to illustrate the merits of the method and to demonstrate the theoretical developments.
---
paper_title: The representer theorem for Hilbert spaces: a necessary and sufficient condition

paper_content:

A family of regularization functionals is said to admit a linear representer theorem if every member of the family admits minimizers that lie in a fixed finite dimensional subspace. A recent characterization states that a general class of regularization functionals with differentiable regularizer admits a linear representer theorem if and only if the regularization term is a non-decreasing function of the norm. In this report, we improve over such result by replacing the differentiability assumption with lower semi-continuity and deriving a proof that is independent of the dimensionality of the space.
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: Gaussian Processes for Machine Learning

paper_content:

Gaussian processes (GPs) provide a principled, practical, probabilistic approach to learning in kernel machines. GPs have received increased attention in the machine-learning community over the past decade, and this book provides a long-needed systematic and unified treatment of theoretical and practical aspects of GPs in machine learning. The treatment is comprehensive and self-contained, targeted at researchers and students in machine learning and applied statistics.The book deals with the supervised-learning problem for both regression and classification, and includes detailed algorithms. A wide variety of covariance (kernel) functions are presented and their properties discussed. Model selection is discussed both from a Bayesian and a classical perspective. Many connections to other well-known techniques from machine learning and statistics are discussed, including support-vector machines, neural networks, splines, regularization networks, relevance vector machines and others. Theoretical issues including learning curves and the PAC-Bayesian framework are treated, and several approximation methods for learning with large datasets are discussed. The book contains illustrative examples and exercises, and code and datasets are available on the Web. Appendixes provide mathematical background and a discussion of Gaussian Markov processes.
---
paper_title: Regularization Theory and Neural Networks Architectures

paper_content:

We had previously shown that regularization principles lead to approximation schemes that are equivalent to networks with one layer of hidden units, called regularization networks . In particular, standard smoothness functionals lead to a subclass of regularization networks, the well known radial basis functions approximation schemes. This paper shows that regularization networks encompass a much broader range of approximation schemes, including many of the popular general additive models and some of the neural networks. In particular, we introduce new classes of smoothness functionals that lead to different classes of basis functions. Additive splines as well as some tensor product splines can be obtained from appropriate classes of smoothness functionals. Furthermore, the same generalization that extends radial basis functions (RBF) to hyper basis functions (HBF) also leads from additive models to ridge approximation models, containing as special cases Breiman's hinge functions, some forms of projection pursuit regression, and several types of neural networks. We propose to use the term generalized regularization networks for this broad class of approximation schemes that follow from an extension of regularization. In the probabilistic interpretation of regularization, the different classes of basis functions correspond to different classes of prior probabilities on the approximating function spaces, and therefore to different types of smoothness assumptions. In summary, different multilayer networks with one hidden layer, which we collectively call generalized regularization networks, correspond to different classes of priors and associated smoothness functionals in a classical regularization principle. Three broad classes are (1) radial basis functions that can be generalized to hyper basis functions, (2) some tensor product splines, and (3) additive splines that can be generalized to schemes of the type of ridge approximation, hinge functions, and several perceptron-like neural networks with one hidden layer.
---
paper_title: VECTOR VALUED REPRODUCING KERNEL HILBERT SPACES OF INTEGRABLE FUNCTIONS AND MERCER THEOREM

paper_content:

We characterize the reproducing kernel Hilbert spaces whose elements are p-integrable functions in terms of the boundedness of the integral operator whose kernel is the reproducing kernel. Moreover, for p = 2, we show that the spectral decomposition of this integral operator gives a complete description of the reproducing kernel, extending the Mercer theorem.
---
paper_title: Reproducing Kernel Hilbert Spaces in Learning Theory

paper_content:

We analyze the regularized least square algorithm in learning theory with Reproducing Kernel Hilbert Spaces (RKHS). Explicit convergence rates for the regression and binary classification problems are obtained in particular for the polynomial and Gaussian kernels on the n-dimensional sphere and the hypercube. There are two major ingredients in our approach: (i) a law of large numbers for Hilbert space-valued random variables; (ii) Mercer's theorem and the spectrum of the integral operator associated with the given reproducing kernel. Our work also illustrates RKHS as a unifying framework for solving many problems encountered in computational learning theory.
---
paper_title: VECTOR VALUED REPRODUCING KERNEL HILBERT SPACES OF INTEGRABLE FUNCTIONS AND MERCER THEOREM

paper_content:

We characterize the reproducing kernel Hilbert spaces whose elements are p-integrable functions in terms of the boundedness of the integral operator whose kernel is the reproducing kernel. Moreover, for p = 2, we show that the spectral decomposition of this integral operator gives a complete description of the reproducing kernel, extending the Mercer theorem.
---
paper_title: Real and Complex Analysis

paper_content:

Preface Prologue: The Exponential Function Chapter 1: Abstract Integration Set-theoretic notations and terminology The concept of measurability Simple functions Elementary properties of measures Arithmetic in [0, ] Integration of positive functions Integration of complex functions The role played by sets of measure zero Exercises Chapter 2: Positive Borel Measures Vector spaces Topological preliminaries The Riesz representation theorem Regularity properties of Borel measures Lebesgue measure Continuity properties of measurable functions Exercises Chapter 3: Lp-Spaces Convex functions and inequalities The Lp-spaces Approximation by continuous functions Exercises Chapter 4: Elementary Hilbert Space Theory Inner products and linear functionals Orthonormal sets Trigonometric series Exercises Chapter 5: Examples of Banach Space Techniques Banach spaces Consequences of Baire's theorem Fourier series of continuous functions Fourier coefficients of L1-functions The Hahn-Banach theorem An abstract approach to the Poisson integral Exercises Chapter 6: Complex Measures Total variation Absolute continuity Consequences of the Radon-Nikodym theorem Bounded linear functionals on Lp The Riesz representation theorem Exercises Chapter 7: Differentiation Derivatives of measures The fundamental theorem of Calculus Differentiable transformations Exercises Chapter 8: Integration on Product Spaces Measurability on cartesian products Product measures The Fubini theorem Completion of product measures Convolutions Distribution functions Exercises Chapter 9: Fourier Transforms Formal properties The inversion theorem The Plancherel theorem The Banach algebra L1 Exercises Chapter 10: Elementary Properties of Holomorphic Functions Complex differentiation Integration over paths The local Cauchy theorem The power series representation The open mapping theorem The global Cauchy theorem The calculus of residues Exercises Chapter 11: Harmonic Functions The Cauchy-Riemann equations The Poisson integral The mean value property Boundary behavior of Poisson integrals Representation theorems Exercises Chapter 12: The Maximum Modulus Principle Introduction The Schwarz lemma The Phragmen-Lindelof method An interpolation theorem A converse of the maximum modulus theorem Exercises Chapter 13: Approximation by Rational Functions Preparation Runge's theorem The Mittag-Leffler theorem Simply connected regions Exercises Chapter 14: Conformal Mapping Preservation of angles Linear fractional transformations Normal families The Riemann mapping theorem The class L Continuity at the boundary Conformal mapping of an annulus Exercises Chapter 15: Zeros of Holomorphic Functions Infinite Products The Weierstrass factorization theorem An interpolation problem Jensen's formula Blaschke products The Muntz-Szas theorem Exercises Chapter 16: Analytic Continuation Regular points and singular points Continuation along curves The monodromy theorem Construction of a modular function The Picard theorem Exercises Chapter 17: Hp-Spaces Subharmonic functions The spaces Hp and N The theorem of F. and M. Riesz Factorization theorems The shift operator Conjugate functions Exercises Chapter 18: Elementary Theory of Banach Algebras Introduction The invertible elements Ideals and homomorphisms Applications Exercises Chapter 19: Holomorphic Fourier Transforms Introduction Two theorems of Paley and Wiener Quasi-analytic classes The Denjoy-Carleman theorem Exercises Chapter 20: Uniform Approximation by Polynomials Introduction Some lemmas Mergelyan's theorem Exercises Appendix: Hausdorff's Maximality Theorem Notes and Comments Bibliography List of Special Symbols Index
---
paper_title: VECTOR VALUED REPRODUCING KERNEL HILBERT SPACES OF INTEGRABLE FUNCTIONS AND MERCER THEOREM

paper_content:

We characterize the reproducing kernel Hilbert spaces whose elements are p-integrable functions in terms of the boundedness of the integral operator whose kernel is the reproducing kernel. Moreover, for p = 2, we show that the spectral decomposition of this integral operator gives a complete description of the reproducing kernel, extending the Mercer theorem.
---
paper_title: Bayesian Function Learning Using MCMC Methods

paper_content:

The paper deals with the problem of reconstructing a continuous 1D function from discrete noisy samples. The measurements may also be indirect in the sense that the samples may be the output of a linear operator applied to the function. Bayesian estimation provides a unified treatment of this class of problems. We show that a rigorous Bayesian solution can be efficiently implemented by resorting to a Markov chain Monte Carlo (MCMC) simulation scheme. In particular, we discuss how the structure of the problem can be exploited in order to improve the computational and convergence performances. The effectiveness of the proposed scheme is demonstrated on two classical benchmark problems as well as on the analysis of IVGTT (IntraVenous glucose tolerance test) data, a complex identification-deconvolution problem concerning the estimation of the insulin secretion rate following the administration of an intravenous glucose injection.
---
paper_title: Markov Chain Monte Carlo in Practice

paper_content:

INTRODUCING MARKOV CHAIN MONTE CARLO Introduction The Problem Markov Chain Monte Carlo Implementation Discussion HEPATITIS B: A CASE STUDY IN MCMC METHODS Introduction Hepatitis B Immunization Modelling Fitting a Model Using Gibbs Sampling Model Elaboration Conclusion MARKOV CHAIN CONCEPTS RELATED TO SAMPLING ALGORITHMS Markov Chains Rates of Convergence Estimation The Gibbs Sampler and Metropolis-Hastings Algorithm INTRODUCTION TO GENERAL STATE-SPACE MARKOV CHAIN THEORY Introduction Notation and Definitions Irreducibility, Recurrence, and Convergence Harris Recurrence Mixing Rates and Central Limit Theorems Regeneration Discussion FULL CONDITIONAL DISTRIBUTIONS Introduction Deriving Full Conditional Distributions Sampling from Full Conditional Distributions Discussion STRATEGIES FOR IMPROVING MCMC Introduction Reparameterization Random and Adaptive Direction Sampling Modifying the Stationary Distribution Methods Based on Continuous-Time Processes Discussion IMPLEMENTING MCMC Introduction Determining the Number of Iterations Software and Implementation Output Analysis Generic Metropolis Algorithms Discussion INFERENCE AND MONITORING CONVERGENCE Difficulties in Inference from Markov Chain Simulation The Risk of Undiagnosed Slow Convergence Multiple Sequences and Overdispersed Starting Points Monitoring Convergence Using Simulation Output Output Analysis for Inference Output Analysis for Improving Efficiency MODEL DETERMINATION USING SAMPLING-BASED METHODS Introduction Classical Approaches The Bayesian Perspective and the Bayes Factor Alternative Predictive Distributions How to Use Predictive Distributions Computational Issues An Example Discussion HYPOTHESIS TESTING AND MODEL SELECTION Introduction Uses of Bayes Factors Marginal Likelihood Estimation by Importance Sampling Marginal Likelihood Estimation Using Maximum Likelihood Application: How Many Components in a Mixture? Discussion Appendix: S-PLUS Code for the Laplace-Metropolis Estimator MODEL CHECKING AND MODEL IMPROVEMENT Introduction Model Checking Using Posterior Predictive Simulation Model Improvement via Expansion Example: Hierarchical Mixture Modelling of Reaction Times STOCHASTIC SEARCH VARIABLE SELECTION Introduction A Hierarchical Bayesian Model for Variable Selection Searching the Posterior by Gibbs Sampling Extensions Constructing Stock Portfolios With SSVS Discussion BAYESIAN MODEL COMPARISON VIA JUMP DIFFUSIONS Introduction Model Choice Jump-Diffusion Sampling Mixture Deconvolution Object Recognition Variable Selection Change-Point Identification Conclusions ESTIMATION AND OPTIMIZATION OF FUNCTIONS Non-Bayesian Applications of MCMC Monte Carlo Optimization Monte Carlo Likelihood Analysis Normalizing-Constant Families Missing Data Decision Theory Which Sampling Distribution? Importance Sampling Discussion STOCHASTIC EM: METHOD AND APPLICATION Introduction The EM Algorithm The Stochastic EM Algorithm Examples GENERALIZED LINEAR MIXED MODELS Introduction Generalized Linear Models (GLMs) Bayesian Estimation of GLMs Gibbs Sampling for GLMs Generalized Linear Mixed Models (GLMMs) Specification of Random-Effect Distributions Hyperpriors and the Estimation of Hyperparameters Some Examples Discussion HIERARCHICAL LONGITUDINAL MODELLING Introduction Clinical Background Model Detail and MCMC Implementation Results Summary and Discussion MEDICAL MONITORING Introduction Modelling Medical Monitoring Computing Posterior Distributions Forecasting Model Criticism Illustrative Application Discussion MCMC FOR NONLINEAR HIERARCHICAL MODELS Introduction Implementing MCMC Comparison of Strategies A Case Study from Pharmacokinetics-Pharmacodynamics Extensions and Discussion BAYESIAN MAPPING OF DISEASE Introduction Hypotheses and Notation Maximum Likelihood Estimation of Relative Risks Hierarchical Bayesian Model of Relative Risks Empirical Bayes Estimation of Relative Risks Fully Bayesian Estimation of Relative Risks Discussion MCMC IN IMAGE ANALYSIS Introduction The Relevance of MCMC to Image Analysis Image Models at Different Levels Methodological Innovations in MCMC Stimulated by Imaging Discussion MEASUREMENT ERROR Introduction Conditional-Independence Modelling Illustrative examples Discussion GIBBS SAMPLING METHODS IN GENETICS Introduction Standard Methods in Genetics Gibbs Sampling Approaches MCMC Maximum Likelihood Application to a Family Study of Breast Cancer Conclusions MIXTURES OF DISTRIBUTIONS: INFERENCE AND ESTIMATION Introduction The Missing Data Structure Gibbs Sampling Implementation Convergence of the Algorithm Testing for Mixtures Infinite Mixtures and Other Extensions AN ARCHAEOLOGICAL EXAMPLE: RADIOCARBON DATING Introduction Background to Radiocarbon Dating Archaeological Problems and Questions Illustrative Examples Discussion Index
---
paper_title: Bayes and empirical Bayes semi-blind deconvolution using eigenfunctions of a prior covariance

paper_content:

We consider the semi-blind deconvolution problem; i.e., estimating an unknown input function to a linear dynamical system using a finite set of linearly related measurements where the dynamical system is known up to some system parameters. Without further assumptions, this problem is often ill-posed and ill-conditioned. We overcome this difficulty by modeling the unknown input as a realization of a stochastic process with a covariance that is known up to some finite set of covariance parameters. We first present an empirical Bayes method where the unknown parameters are estimated by maximizing the marginal likelihood/posterior and subsequently the input is reconstructed via a Tikhonov estimator (with the parameters set to their point estimates). Next, we introduce a Bayesian method that recovers the posterior probability distribution, and hence the minimum variance estimates, for both the unknown parameters and the unknown input function. Both of these methods use the eigenfunctions of the random process covariance to obtain an efficient representation of the unknown input function and its probability distributions. Simulated case studies are used to test the two methods and compare their relative performance.
---
paper_title: A unifying view of sparse approximate Gaussian process regression

paper_content:

We provide a new unifying view, including all existing proper probabilistic sparse approximations for Gaussian process regression. Our approach relies on expressing the effective prior which the methods are using. This allows new insights to be gained, and highlights the relationship between existing methods. It also allows for a clear theoretically justified ranking of the closeness of the known approximations to the corresponding full GPs. Finally we point directly to designs of new better sparse approximations, combining the best of the existing strategies, within attractive computational constraints.
---
paper_title: On the MSE Properties of Empirical Bayes Methods for Sparse Estimation

paper_content:

Abstract Popular convex approaches for sparse estimation such as Lasso and Multiple Kernel Learning (MKL) can be derived in a Bayesian setting, starting from a particular stochastic model. In problems where groups of variables have to be estimated, we show that the same probabilistic model, under a suitable marginalization, leads to a different non-convex estimator where hyperparameters are optimized. Theoretical arguments, independent of the correctness of the priors entering the sparse model, are included to clarify the advantages of our non-convex technique in comparison with MKL and the group version of Lasso under assumption of orthogonal regressors.
---
paper_title: Spline Models for Observational Data.

paper_content:

Foreword 1. Background 2. More splines 3. Equivalence and perpendicularity, or, what's so special about splines? 4. Estimating the smoothing parameter 5. 'Confidence intervals' 6. Partial spline models 7. Finite dimensional approximating subspaces 8. Fredholm integral equations of the first kind 9. Further nonlinear generalizations 10. Additive and interaction splines 11. Numerical methods 12. Special topics Bibliography Author index.
---
paper_title: Smoothing noisy data with spline functions

paper_content:

It is shown how to choose the smoothing parameter when a smoothing periodic spline of degree 2m−1 is used to reconstruct a smooth periodic curve from noisy ordinate data. The noise is assumed “white”, and the true curve is assumed to be in the Sobolev spaceW2(2m) of periodic functions with absolutely continuousv-th derivative,v=0, 1, ..., 2m−1 and square integrable 2m-th derivative. The criteria is minimum expected square error, averaged over the data points. The dependency of the optimum smoothing parameter on the sample size, the noise variance, and the smoothness of the true curve is found explicitly.
---
paper_title: Use of PRESS residuals in dynamic system identification

paper_content:

Cross-validation, whereby the data is split into an estimation set and a prediction set, is often used for model structure selection in dynamic system identification. A related approach that simulates cross-validation without requiring two sets of data is to compute the weighted residuals of the least-squares estimated model that represent the true prediction errors. The sum of the squared true prediction errors is defined as the PRESS. This paper will show that the computation of the PRESS is straightforward when using an orthogonal decomposition algorithm to obtain the least squares model parameter estimates. A benchmark example of Ljung is used to illustrate how the PRESS is applied for model structure selection.
---
paper_title: Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter

paper_content:

Consider the ridge estimate (λ) for β in the model unknown, (λ) = (X T X + nλI)−1 X T y. We study the method of generalized cross-validation (GCV) for choosing a good value for λ from the data. The estimate is the minimizer of V(λ) given by where A(λ) = X(X T X + nλI)−1 X T . This estimate is a rotation-invariant version of Allen's PRESS, or ordinary cross-validation. This estimate behaves like a risk improvement estimator, but does not require an estimate of σ2, so can be used when n − p is small, or even if p ≥ 2 n in certain cases. The GCV method can also be used in subset selection and singular value truncation methods for regression, and even to choose from among mixtures of these methods.
---
paper_title: Learning low-rank kernel matrices

paper_content:

Kernel learning plays an important role in many machine learning tasks. However, algorithms for learning a kernel matrix often scale poorly, with running times that are cubic in the number of data points. In this paper, we propose efficient algorithms for learning low-rank kernel matrices; our algorithms scale linearly in the number of data points and quadratically in the rank of the kernel. We introduce and employ Bregman matrix divergences for rank-deficient matrices---these divergences are natural for our problem since they preserve the rank as well as positive semi-definiteness of the kernel matrix. Special cases of our framework yield faster algorithms for various existing kernel learning problems. Experimental results demonstrate the effectiveness of our algorithms in learning both low-rank and full-rank kernels.
---
paper_title: A General Convergence Theorem for the Decomposition Method

paper_content:

The decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with support vector machines. Although there exist some versions of the method that are known to converge to an optimal solution, the general convergence properties of the method are not yet fully understood. In this paper, we present a variant of the decomposition method that basically converges for any convex quadratic optimization problem provided that the policy for working set selection satisfies three abstract conditions. We furthermore design a concrete policy that meets these requirements.
---
paper_title: Bayes and empirical Bayes semi-blind deconvolution using eigenfunctions of a prior covariance

paper_content:

We consider the semi-blind deconvolution problem; i.e., estimating an unknown input function to a linear dynamical system using a finite set of linearly related measurements where the dynamical system is known up to some system parameters. Without further assumptions, this problem is often ill-posed and ill-conditioned. We overcome this difficulty by modeling the unknown input as a realization of a stochastic process with a covariance that is known up to some finite set of covariance parameters. We first present an empirical Bayes method where the unknown parameters are estimated by maximizing the marginal likelihood/posterior and subsequently the input is reconstructed via a Tikhonov estimator (with the parameters set to their point estimates). Next, we introduce a Bayesian method that recovers the posterior probability distribution, and hence the minimum variance estimates, for both the unknown parameters and the unknown input function. Both of these methods use the eigenfunctions of the random process covariance to obtain an efficient representation of the unknown input function and its probability distributions. Simulated case studies are used to test the two methods and compare their relative performance.
---
paper_title: Bayesian regression filters and the issue of priors

paper_content:

We propose a Bayesian framework for regression problems, which covers areas usually dealt with by function approximation. An online learning algorithm is derived which solves regression problems with a Kalman filter. Its solution always improves with increasing model complexity, without the risk of over-fitting. In the infinite dimension limit it approaches the true Bayesian posterior. The issues of prior selection and over-fitting are also discussed, showing that some of the commonly held beliefs are misleading. The practical implementation is summarised. Simulations using 13 popular publicly available data sets are used to demonstrate the method and highlight important issues concerning the choice of priors.
---
paper_title: Regularization paths for generalized linear models via coordinate descent

paper_content:

We develop fast algorithms for estimation of generalized linear models with convex penalties. The models include linear regression, two-class logistic regression, and multi- nomial regression problems while the penalties include l1 (the lasso), l2 (ridge regression) and mixtures of the two (the elastic net). The algorithms use cyclical coordinate descent, computed along a regularization path. The methods can handle large problems and can also deal efficiently with sparse features. In comparative timings we find that the new algorithms are considerably faster than competing methods.
---
paper_title: Sparse Spectrum Gaussian Process Regression

paper_content:

We present a new sparse Gaussian Process (GP) model for regression. The key novel idea is to sparsify the spectral representation of the GP. This leads to a simple, practical algorithm for regression tasks. We compare the achievable trade-offs between predictive accuracy and computational requirements, and show that these are typically superior to existing state-of-the-art sparse approximations. We discuss both the weight space and function space representations, and note that the new construction implies priors over functions which are always stationary, and can approximate any covariance function in this class.
---
paper_title: Using the Nyström Method to Speed Up Kernel Machines

paper_content:

A major problem for kernel-based predictors (such as Support Vector Machines and Gaussian processes) is that the amount of computation required to find the solution scales as O(n3), where n is the number of training examples. We show that an approximation to the eigendecomposition of the Gram matrix can be computed by the Nystrom method (which is used for the numerical solution of eigenproblems). This is achieved by carrying out an eigendecomposition on a smaller system of size m < n, and then expanding the results back up to n dimensions. The computational complexity of a predictor using this approximation is O(m2n). We report experiments on the USPS and abalone data sets and show that we can set m ≪ n without any significant decrease in the accuracy of the solution.
---
paper_title: Finite-Dimensional Approximation of Gaussian Processes

paper_content:

Gaussian process (GP) prediction suffers from O(n3) scaling with the data set size n. By using a finite-dimensional basis to approximate the GP predictor, the computational complexity can be reduced. We derive optimal finite-dimensional predictors under a number of assumptions, and show the superiority of these predictors over the Projected Bayes Regression method (which is asymptotically optimal). We also show how to calculate the minimal model size for a given n. The calculations are backed up by numerical experiments.
---
paper_title: On the mathematical foundations of learning

paper_content:

(1) A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference). We try to emphasize relations of the theory of learning to the mainstream of mathematics. In particular, there are large roles for probability theory, for algorithms such as least squares, and for tools and ideas from linear algebra and linear analysis. An advantage of doing this is that communication is facilitated and the power of core mathematics is more easily brought to bear. We illustrate what we mean by learning theory by giving some instances. (a) The understanding of language acquisition by children or the emergence of languages in early human cultures. (b) In Manufacturing Engineering, the design of a new wave of machines is anticipated which uses sensors to sample properties of objects before, during, and after treatment. The information gathered from these samples is to be analyzed by the machine to decide how to better deal with new input objects (see [43]). (c) Pattern recognition of objects ranging from handwritten letters of the alphabet to pictures of animals, to the human voice. Understanding the laws of learning plays a large role in disciplines such as (Cognitive) Psychology, Animal Behavior, Economic Decision Making, all branches of Engineering, Computer Science, and especially the study of human thought processes (how the brain works). Mathematics has already played a big role towards the goal of giving a universal foundation of studies in these disciplines. We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments. We are heavily indebted to these developments. Recent discussions with a number of mathematicians have also been helpful. In
---
paper_title: Predictive low-rank decomposition for kernel methods

paper_content:

Low-rank matrix decompositions are essential tools in the application of kernel methods to large-scale learning problems. These decompositions have generally been treated as black boxes---the decomposition of the kernel matrix that they deliver is independent of the specific learning task at hand---and this is a potentially significant source of inefficiency. In this paper, we present an algorithm that can exploit side information (e.g., classification labels, regression responses) in the computation of low-rank decompositions for kernel matrices. Our algorithm has the same favorable scaling as state-of-the-art methods such as incomplete Cholesky decomposition---it is linear in the number of data points and quadratic in the rank of the approximation. We present simulation results that show that our algorithm yields decompositions of significantly smaller rank than those found by incomplete Cholesky decomposition.
---
paper_title: A unifying view of sparse approximate Gaussian process regression

paper_content:

We provide a new unifying view, including all existing proper probabilistic sparse approximations for Gaussian process regression. Our approach relies on expressing the effective prior which the methods are using. This allows new insights to be gained, and highlights the relationship between existing methods. It also allows for a clear theoretically justified ranking of the closeness of the known approximations to the corresponding full GPs. Finally we point directly to designs of new better sparse approximations, combining the best of the existing strategies, within attractive computational constraints.
---
paper_title: Clustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction

paper_content:

Kernel (or similarity) matrix plays a key role in many machine learning algorithms such as kernel methods, manifold learning, and dimension reduction. However, the cost of storing and manipulating the complete kernel matrix makes it infeasible for large problems. The Nystrom method is a popular sampling-based low-rank approximation scheme for reducing the computational burdens in handling large kernel matrices. In this paper, we analyze how the approximating quality of the Nystrom method depends on the choice of landmark points, and in particular the encoding powers of the landmark points in summarizing the data. Our (non-probabilistic) error analysis justifies a “clustered Nystrom method” that uses the k-means clustering centers as landmark points. Our algorithm can be applied to scale up a wide variety of algorithms that depend on the eigenvalue decomposition of kernel matrix (or its variant), such as kernel principal component analysis, Laplacian eigenmap, spectral clustering, as well as those involving kernel matrix inverse such as least-squares support vector machine and Gaussian process regression. Extensive experiments demonstrate the competitive performance of our algorithm in both accuracy and efficiency.
---
paper_title: Gaussian Regression and Optimal Finite Dimensional Linear Models

paper_content:

The problem of regression under Gaussian assumptions is treated generally. The relationship between Bayesian prediction, regularization and smoothing is elucidated. The ideal regression is the posterior mean and its computation scales as O(n 3 ) , where n is the sample size. We show that the optimal m -dimensional linear model under a given prior is spanned by the first m eigenfunctions of a covariance operator, which is a trace-class operator. This is an infinite dimensional analogue of principal component analysis. The importance of Hilbert space methods to practical statistics is also discussed.
---
paper_title: The Interplay of Optimization and Machine Learning Research

paper_content:

The fields of machine learning and mathematical programming are increasingly intertwined. Optimization problems lie at the heart of most machine learning approaches. The Special Topic on Machine Learning and Large Scale Optimization examines this interplay. Machine learning researchers have embraced the advances in mathematical programming allowing new types of models to be pursued. The special topic includes models using quadratic, linear, second-order cone, semi-definite, and semi-infinite programs. We observe that the qualities of good optimization algorithms from the machine learning and optimization perspectives can be quite different. Mathematical programming puts a premium on accuracy, speed, and robustness. Since generalization is the bottom line in machine learning and training is normally done off-line, accuracy and small speed improvements are of little concern in machine learning. Machine learning prefers simpler algorithms that work in reasonable computational time for specific classes of problems. Reducing machine learning problems to well-explored mathematical programming classes with robust general purpose optimization codes allows machine learning researchers to rapidly develop new techniques. In turn, machine learning presents new challenges to mathematical programming. The special issue include papers from two primary themes: novel machine learning models and novel optimization approaches for existing models. Many papers blend both themes, making small changes in the underlying core mathematical program that enable the develop of effective new algorithms.
---
paper_title: Theoretical Basis of Indicator-Dilution Methods For Measuring Flow and Volume

paper_content:

An apparatus for determining and/or monitoring the amount of particulate material in an accumulator, which material enters the accumulator at a temperature above the ambient temperature, comprising an accumulator body for holding particulate material; an inlet means located in the upper portion of the accumulator body to allow the particulate material to enter the accumulator body; and a plurality of temperature sensing means located at points of differing height in the accumulator body below the inlet means.
---
paper_title: Measuring Cerebral Blood Flow Using Magnetic Resonance Imaging Techniques

paper_content:

Magnetic resonance imaging techniques measuring CBF have developed rapidly in the last decade, resulting in a wide range of available methods. The most successful approaches are based either on dynamic tracking of a bolus of a paramagnetic contrast agent (dynamic susceptibility contrast) or on arterial spin labeling. This review discusses their principles, possible pitfalls, and potential for absolute quantification and outlines clinical and neuroscientific applications.
---
paper_title: Nonlinear Stochastic Regularization to Characterize Tissue Residue Function in Bolus-Tracking MRI: Assessment and Comparison With SVD, Block-Circulant SVD, and Tikhonov

paper_content:

An accurate characterization of tissue residue function R(t) in bolus-tracking magnetic resonance imaging is of crucial importance to quantify cerebral hemodynamics. R(t) estimation requires to solve a deconvolution problem. The most popular deconvolution method is singular value decomposition (SVD). However, SVD is known to bear some limitations, e.g., R(t) profiles exhibit nonphysiological oscillations and take on negative values. In addition, SVD estimates are biased in presence of bolus delay and dispersion. Recently, other deconvolution methods have been proposed, in particular block-circulant SVD (cSVD) and Tikhonov regularization (TIKH). Here we propose a new method based on nonlinear stochastic regularization (NSR). NSR is tested on simulated data and compared with SVD, cSVD, and TIKH in presence and absence of bolus dispersion. A clinical case in one patient has also been considered. NSR is shown to perform better than SVD, cSVD, and TIKH in reconstructing both the peak and the residue function, in particular when bolus dispersion is considered. In addition, differently from SVD, cSVD, and TIKH, NSR always provides positive and smooth R(t).
---
paper_title: Reweighted nuclear norm minimization with application to system identification

paper_content:

The matrix rank minimization problem consists of finding a matrix of minimum rank that satisfies given convex constraints. It is NP-hard in general and has applications in control, system identification, and machine learning. Reweighted trace minimization has been considered as an iterative heuristic for this problem. In this paper, we analyze the convergence of this iterative heuristic, showing that the difference between successive iterates tends to zero. Then, after reformulating the heuristic as reweighted nuclear norm minimization, we propose an efficient gradient-based implementation that takes advantage of the new formulation and opens the way to solving large-scale problems. We apply this algorithm to the problem of low-order system identification from input-output data. Numerical examples demonstrate that the reweighted nuclear norm minimization makes model order selection easier and results in lower order models compared to nuclear norm minimization without weights.
---
paper_title: Linear system identification via atomic norm regularization

paper_content:

This paper proposes a new algorithm for linear system identification from noisy measurements. The proposed algorithm balances a data fidelity term with a norm induced by the set of single pole filters. We pose a convex optimization problem that approximately solves the atomic norm minimization problem and identifies the unknown system from noisy linear measurements. This problem can be solved efficiently with standard, free software. We provide rigorous statistical guarantees that explicitly bound the estimation error (in the ℌ 2 -norm) in terms of the stability radius, the Hankel singular values of the true system and the number of measurements. These results in turn yield complexity bounds and asymptotic consistency. We provide numerical experiments demonstrating the efficacy of our method for estimating linear systems from a variety of linear measurements.
---
paper_title: Regularization strategies for nonparametric system identification

paper_content:

In the recent years several regularization strategies have been proposed to tackle linear system identification problems. One line of work has concentrated on designing and studying the properties of several Kernels for l2-type regularization in impulse response estimation; a second stream of work has proposed using Nuclear Norm type of penalties on certain Hankel data matrices, aiming at favoring (almost) low rank solutions in subspace type procedures. The goal of this paper is twofold: (i) bring all these ideas under a common umbrella also proposing an algorithm which combines different penalties and (ii) provide a first comparison between different approaches.
---
paper_title: System identification via nuclear norm regularization for simulated moving bed processes from incomplete data sets

paper_content:

The application of nuclear norm regularization to system identification was recently shown to be a useful method for identifying low order linear models. In this paper, we consider nuclear norm regularization for identification of simulated moving bed processes from data sets with missing entries. The missing data problem is of ongoing interest because the need to analyze incomplete data sets arises frequently in diverse fields such as chemistry, psychometrics and satellite imaging. By casting system identification as a convex optimization problem, nuclear norm regularization can be applied to identify the system in one step, i.e., without imputation of the missing data. Our exploratory work compares the proposed method named NucID to the standard techniques N4SID, prediction error minimization, subspace identification and expectation conditional maximization via linear regression and a linearized first principles model. NucID is found to consistently identify systems with missing data within the imposed error tolerance, a task for which the standard methods sometimes fail, and to be particularly effective when the data is missing with patterns, e.g., on multi-rate systems, where it significantly outperforms existing procedures.
---
paper_title: A rank minimization heuristic with application to minimum order system approximation

paper_content:

We describe a generalization of the trace heuristic that applies to general nonsymmetric, even non-square, matrices, and reduces to the trace heuristic when the matrix is positive semidefinite. The heuristic is to replace the (nonconvex) rank objective with the sum of the singular values of the matrix, which is the dual of the spectral norm. We show that this problem can be reduced to a semidefinite program, hence efficiently solved. To motivate the heuristic, we, show that the dual spectral norm is the convex envelope of the rank on the set of matrices with norm less than one. We demonstrate the method on the problem of minimum-order system approximation.
---
paper_title: Convex estimation of cointegrated VAR models by a nuclear norm penalty

paper_content:

Abstract Cointegrated Vector AutoRegressive (VAR) processes arise in the study of long run equilibrium relations of stochastic dynamical systems. In this paper we introduce a novel convex approach for the analysis of these type of processes. The idea relies on an error correction representation and amounts at solving a penalized empirical risk minimization problem. The latter finds a model from data by minimizing a trade-off between a quadratic error function and a nuclear norm penalty used as a proxy for the cointegrating rank. We elaborate on properties of the proposed convex program; we then propose an easily implementable and provably convergent algorithm based on FISTA. This algorithm can be conveniently used for computing the regularization path, i.e., the entire set of solutions associated to the trade-off parameter. We show how such path can be used to build an estimator for the cointegrating rank and illustrate the proposed ideas with experiments.
---
paper_title: Interior-Point Method for Nuclear Norm Approximation with Application to System Identification

paper_content:

The nuclear norm (sum of singular values) of a matrix is often used in convex heuristics for rank minimization problems in control, signal processing, and statistics. Such heuristics can be viewed as extensions of $\ell_1$-norm minimization techniques for cardinality minimization and sparse signal estimation. In this paper we consider the problem of minimizing the nuclear norm of an affine matrix-valued function. This problem can be formulated as a semidefinite program, but the reformulation requires large auxiliary matrix variables, and is expensive to solve by general-purpose interior-point solvers. We show that problem structure in the semidefinite programming formulation can be exploited to develop more efficient implementations of interior-point methods. In the fast implementation, the cost per iteration is reduced to a quartic function of the problem dimensions and is comparable to the cost of solving the approximation problem in the Frobenius norm. In the second part of the paper, the nuclear norm approximation algorithm is applied to system identification. A variant of a simple subspace algorithm is presented in which low-rank matrix approximations are computed via nuclear norm minimization instead of the singular value decomposition. This has the important advantage of preserving linear matrix structure in the low-rank approximation. The method is shown to perform well on publicly available benchmark data.
---
paper_title: The Convex Geometry of Linear Inverse Problems

paper_content:

In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered are those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases such as sparse vectors and low-rank matrices, as well as several others including sums of a few permutations matrices, low-rank tensors, orthogonal matrices, and atomic measures. The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery. Thus this work extends the catalog of simple models that can be recovered from limited linear information via tractable convex programming.
---
paper_title: Nuclear norm regularization for overparametrized Hammerstein systems

paper_content:

In this paper we study the overparametrization scheme for Hammerstein systems [1] in the presence of regularization. The quality of the convex approximation is analysed, that is obtained by relaxing the implicit rank one constraint. To obtain an improved convex relaxation we propose the use of nuclear norms [2], instead of using ridge regression. On several simple examples we illustrate that this yields a solution close to the best possible convex approximation. Furthermore the experiments suggest that ridge regression in combination with a projection step yield a generalization performance close to the one obtained by nuclear norms.
---
paper_title: Sparse estimation based on a validation criterion

paper_content:

A sparse estimator with close ties with the LASSO (least absolute shrinkage and selection operator) is analysed. The basic idea of the estimator is to relax the least-squares cost function to what the least-squares method would achieve on validation data and then use this as a constraint in the minimization of the l 1 -norm of the parameter vector. In a linear regression framework, exact conditions are established for when the estimator is consistent in probability and when it possesses sparseness. By adding a re-estimation step, where least-squares is used to re-estimate the non-zero elements of the parameter vector, the so called Oracle property can be obtained, i.e. the estimator achieves the asymptotic Cramer-Rao lower bound corresponding to when it is known which regressors are active. The method is shown to perform favourably compared to other methods on a simulation example.
---
paper_title: Regression Shrinkage and Selection Via the Lasso

paper_content:

SUMMARY We propose a new method for estimation in linear models. The 'lasso' minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant. Because of the nature of this constraint it tends to produce some coefficients that are exactly 0 and hence gives interpretable models. Our simulation studies suggest that the lasso enjoys some of the favourable properties of both subset selection and ridge regression. It produces interpretable models like subset selection and exhibits the stability of ridge regression. There is also an interesting relationship with recent work in adaptive function estimation by Donoho and Johnstone. The lasso idea is quite general and can be applied in a variety of statistical models: extensions to generalized regression models and tree-based models are briefly described.
---
paper_title: HANKEL MATRIX RANK MINIMIZATION WITH APPLICATIONS TO SYSTEM IDENTIFICATION AND REALIZATION ∗

paper_content:

We introduce a flexible optimization framework for nuclear norm minimization of matrices with linear structure, including Hankel, Toeplitz, and moment structures and catalog applications from diverse fields under this framework. We discuss various first-order methods for solving the resulting optimization problem, including alternating direction methods of multipliers, proximal point algorithms, and gradient projection methods. We perform computational experiments to compare these methods on system identification problems and system realization problems. For the system identification problem, the gradient projection method (accelerated by Nesterov's extrapolation techniques) and the proximal point algorithm usually outperform other first-order methods in terms of CPU time on both real and simulated data, for small and large regularization parameters, respectively, while for the system realization problem, the alternating direction method of multipliers, as applied to a certain primal reformulation, usuall...
---
paper_title: A sparse estimation technique for general model structures

paper_content:

In this paper, a general sparse estimator is proposed, based on the maximum likelihood / prediction error method (or any √N-consistent estimator). This procedure does not rely on the convexity of the cost function of the underlying estimator (in case such estimator is an M-estimator), and it provides an automatic tuning of the (implicit) regularization parameter. The idea behind the proposed method is a three step procedure, where the first step consists in a standard √N-consistent estimation, the second step seeks for the sparsest estimate in a neighborhood of the initial estimate, and the last step is a refinement based on the sparseness pattern estimated in the second step. A rigorous statistical analysis is provided, which establishes conditions for consistency, asymptotic variable selection and the so-called Oracle property. A simulation example is given to demonstrate the performance of the method.
---

Title: Survey Kernel methods in system identification, machine learning and function estimation: A survey

Section 1: Estimating system impulse responses in discrete time
Description 1: In this part, we study the problem of estimating system impulse responses in discrete time.

Section 2: System identification
Description 2: There is a very extensive literature on system identification, with many textbooks covering classical methods like Maximum Likelihood (ML).

Section 3: Parametric model structures
Description 3: A model structure M is a parameterized collection of models that describe the relations between the input and output signal of the system.

Section 4: Fitting time-domain data
Description 4: Discusses how collected time-domain data are compared with model predicted values to form the criterion of fit, defining the parameter estimation method.

Section 5: Bias and variance
Description 5: This section explores the impact of noise and disturbances on the observations and the resultant bias and variance in model estimation.

Section 6: Adjusting the estimation criterion
Description 6: With increasing model flexibility, a penalty for model flexibility is added to account for the total quality of the model.

Section 7: Cross validation
Description 7: Another important technique for model selection is cross validation, which estimates the prediction capability of future data of the model in correspondence with different choices of parameters.

Section 8: Regularization of linear regression models
Description 8: It includes principles and methods for regularizing linear regression models to handle cases like singular or ill-conditioned scenarios.

Section 9: Linear regression models
Description 9: Provides a general discussion on the form and estimation techniques for linear regression models.

Section 10: Regularized least squares
Description 10: Discusses the regularized least squares (ReLS) method for improving the numerical properties and decreasing the variance of the estimator.

Section 11: Bayesian interpretation
Description 11: Links the regularized least squares estimate to the Bayesian framework, interpreting regularization matrices as prior covariance matrices.

Section 12: Tuning the regularization: marginal likelihood maximization
Description 12: Explores methods for estimating the regularization matrix using the principle of marginal likelihood maximization.

Section 13: Regularization in system identification
Description 13: Examines the application of regularization techniques to system identification, introducing suitable regularization matrices.

Section 14: FIR models
Description 14: Discusses the specific application of regularization techniques to FIR models in system identification.

Section 15: Multi-input FIR-models
Description 15: Extends the regularization methods to scenarios with multiple input FIR models.

Section 16: General predictor models and ARX models
Description 16: Considers how general predictor models and ARX models can be regularized using the discussed techniques.

Section 17: Regularized least squares and James-Stein estimators ⋆
Description 17: Examines the relationship between ReLS and the James-Stein estimator, including performance discussions.

Section 18: Numerical illustrations
Description 18: Presents Monte Carlo experiments and other numerical examples to illustrate the performance of the algorithms discussed.

Section 19: Function estimation by regularized kernel methods
Description 19: Discusses the general theory and application of regularized kernel methods for function estimation.

Section 20: Reproducing kernel Hilbert spaces
Description 20: Introduces reproducing kernel Hilbert spaces (RKHS) and their properties in the context of regularization and ill-posed problems.

Section 21: The representer theorem
Description 21: Highlights a key result showing that solutions to certain variational problems in RKHS admit finite-dimensional representations.

Section 22: The bias space ⋆
Description 22: Discusses the inclusion of low-dimensional parametric parts (bias space) to enrich the RKHS and improve function estimates.

Section 23: Kernels
Description 23: Overview of various positive semidefinite kernels used in RKHS-based function estimation, including specific examples.

Section 24: Linear kernels and regularized linear regression ⋆
Description 24: Explores linear kernels and their application to regularized linear regression.

Section 25: Kernels given by a finite number of basis functions
Description 25: Discusses kernels constructed from a finite set of basis functions and their implications for RKHS.

Section 26: Radial basis kernels
Description 26: Introduction to radial basis function kernels and their use in nonparametric estimation.

Section 27: Spline kernels
Description 27: Insight into spline kernels, especially cubic splines, and their role in RKHS regularization.

Section 28: Numerical example using the cubic spline estimator
Description 28: Provides a numerical example illustrating the impact of the regularization parameter on estimator performance using cubic splines.

Section 29: Concluding remarks of the section
Description 29: Summarizes the key points of section 19 on function estimation by regularized kernel methods.

Section 30: Continuous-time system identification as a function estimation problem
Description 30: Discusses the extension of function estimation techniques to the problem of continuous-time system identification.

Section 31: Impulse response estimation problem
Description 31: Focuses on the problem of reconstructing the impulse response of a continuous-time linear system from observed data.

Section 32: Regularized identification in RKHS and the representer theorem for system identification
Description 32: Adaptation of the representer theorem to continuous-time system identification problems within the RKHS framework.

Section 33: Regularized FIR estimation as regularization in RKHS⋆
Description 33: Discusses the connection of RKHS theory with regularized FIR estimation and the nature of the associated RKHS norm.

Section 34: Connection with Bayesian estimation of continuous-time Gaussian stochastic processes
Description 34: Establishes the probabilistic interpretation of regularized function estimation as Bayesian estimation of Gaussian processes.

Section 35: The Gaussian and the cubic spline kernels are not suited to impulse response estimation
Description 35: Demonstrates why standard machine learning kernels like the Gaussian and cubic spline are inadequate for impulse response estimation in system identification.

Section 36: The notion of stable kernel and sufficient conditions for kernel stability
Description 36: Introduces the concept of stable kernels suitable for system identification and discusses their necessary and sufficient conditions.

Section 37: The necessary and sufficient condition for kernel stability
Description 37: Extends the discussion on kernel stability by providing precise mathematical conditions for kernel stability.

Section 38: The optimal continuous-time kernel
Description 38: Derives the notion of an optimal continuous-time kernel based on the minimization of the mean square error (MSE).

Section 39: Stable spline kernels and their relationship with TC and SS
Description 39: Introduction to stable spline kernels and their deep connection with Tuned Correlated (TC) and Stable Spline (SS) kernels.

Section 40: Tuning of the design parameters
Description 40: Discusses different strategies for tuning kernel and regularization parameters, which is crucial for the performance of identification techniques.

Section 41: Marginal likelihood optimization
Description 41: Explores the use of marginal likelihood optimization for tuning design parameters and discuss its theoretical underpinnings and practical implementations.

Section 42: C p statistics
Description 42: Discusses the use of C p statistics for model selection in function estimation.

Section 43: Cross validation, PRESS and GCV
Description 43: Explores various cross-validation methods, including PRESS and generalized cross-validation (GCV), for model tuning in the function estimation context.

Section 44: Computational issues
Description 44: Reviews the computational challenges and solutions in implementing regularized function estimation techniques.

Section 45: Continuous-time example: estimation of cerebral hemodynamics
Description 45: Provides a real-world application of continuous-time system identification to cerebral hemodynamics using regularized estimation methods.

Section 46: Other regularization techniques for system identification
Description 46: Overview of alternative regularization techniques beyond quadratic penalties, such as ℓ 1 and nuclear norm penalties, and their applications in system identification.

Section 47: Conclusions
Description 47: Summarizes the survey, highlighting the broad approach to system identification and the significant insights gained from RKHS-based function estimation and kernel methods.