nils-herrmann/clean_scirepeval huggingface dataset:
On the Relationship between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions

Feedforward networks together with their training algorithms are a class of regression techniques that can be used to learn to perform some task from a set of examples. The question of generalization of network performance from a finite training set to unseen data is clearly of crucial importance. In this article we first show that the generalization error can be decomposed into two terms: the approximation error, due to the insufficient representational capacity of a finite sized network, and the estimation error, due to insufficient information about the target function because of the finite number of samples. We then consider the problem of learning functions belonging to certain Sobolev spaces with gaussian radial basis functions. Using the above-mentioned decomposition we bound the generalization error in terms of the number of basis functions and number of examples. While the bound that we derive is specific for radial basis functions, a number of observations deriving from it apply to any approximation technique. Our result also sheds light on ways to choose an appropriate network architecture for a particular problem and the kinds of problems that can be effectively solved with finite resources, i.e., with a finite number of parameters and finite amounts of data.
A Note on Zipf's Law, Natural Languages, and Noncoding DNA regions

, Mantegna et al. conclude on the basis of Zipf rank frequency data that noncoding DNA sequence regions are more like natural languages than coding regions. We argue on the contrary that an empirical fit to Zipf''s "law" cannot be used as a criterion for similarity to natural languages. Although DNA is a presumably "organized system of signs" in Mandelbrot''s (1961) sense, and observation of statistical featurs of the sort presented in the Mantegna et al. paper does not shed light on the similarity between DNA''s "gramar" and natural language grammars, just as the observation of exact Zipf-like behavior cannot distinguish between the underlying processes of tossing an M-sided die or a finite-state branching process.
The informational complexity of learning from examples

This thesis attempts to quantify the amount of information needed to learn certain tasks. The tasks chosen vary from learning functions in a Sobolev space using radial basis function networks to learning grammars in the principles and parameters framework of modern linguistic theory. These problems are analyzed from the perspective of computational learning theory and certain unifying perspectives emerge.  This report describes research done within the Center for Biological and Computational Learning in the Department of Brain and Cognitive Sciences and at the Arti cial Intelligence Laboratory at the Massachusetts Institute of Technology. This research is sponsored by a grant from the National Science Foundation under contract ASC-9217041 (this award includes funds from ARPA provided under the HPCC program); and by a grant from ARPA/ONR under contract N00014-92-J-1879. Additional support has been provided by Siemens Corporate Research Inc., Mitsubishi Electric Corporation and Sumitomo Metal Industries. Support for the A.I. Laboratory's arti cial intelligence research is provided by ARPA contract N00014-91-J-4038. The Informational Complexity of Learning from
The Logical Problem of Language Change

This paper considers the problem of language change. Linguists must explain not only how languages are learned but also how and why they have evolved along certain trajectories and not others. While the language learning problem has focused on the behavior of individuals and how they acquire a particular grammar from a class of grammars ${\cal G}$, here we consider a {\it population\/} of such learners and investigate the emergent, global population characteristics of linguistic communities over several generations. We argue that language change follows logically from specific assumptions about grammatical theories and learning paradigms. In particular, we are able to transform parameterized theories and memoryless acquisition algorithms into grammatical dynamical systems, whose evolution depicts a population''s evolving linguistic composition. We investigate the linguistic and computational consequences of this model, showing that the formalization allows one to ask questions about diachronic that one otherwise could not ask, such as the effect of varying initial conditions on the resulting diachronic trajectories. From a more programmatic perspective, we give an example of how the dynamical system model for language change can serve as a way to distinguish among alternative grammatical theories, introducing a formal diachronic adequacy criterion for linguistic theories.
Sequential Optimal Recovery: A Paradigm for Active Learning.

In most classical frameworks for learning from examples, it is assumed that examples are randomly drawn and presented to the learner. In this paper, we consider the possibility of a more (it active) learner who is allowed to choose his/her own examples. Our investigations are carried out in a function approximation setting. In particular, using arguments from optimal recovery, we develop an adaptive sampling strategy (equivalent to adaptive approximation) for arbitrary approximation schemes. We provide a general formulation of the problem and show how it can be regarded as sequential optimal recovery. We demonstrate the application of this general formulation to two special cases of functions on the real line monotonically increasing functions and functions with bounded derivative. An extensive investigation of the sample complexity of approximating these functions is conducted yielding both theoretical and empirical results on test functions. Our theoretical results (stated in PAC-style), along with the simulations demonstrate the superiority of our active scheme over both passive learning as well as classical optimal recovery. The analysis of active function approximation is conducted in a worst-case setting, in contrast with other Bayesian paradigms obtained from optimal design.
A Formulation for Active Learning with Applications to Object Detection

We discuss a formulation for active example selection for function learning problems. This formulation is obtained by adapting Fedorov''s optimal experiment design to the learning problem. We specifically show how to {\it analytically} derive example selection algorithms for certain well defined function classes. We then explore the behavior and sample complexity of such active learning algorithms. Finally, we view object detection as a special case of function learning and show how our formulation reduces to a useful heuristic to choose examples to reduce the generalization error.
Active learning the weights of a RBF network

We describe a principled strategy to sample functions optimally for function approximation tasks. The strategy works within a Bayesian framework and uses ideas from optimal experiment design to evaluate the potential utility of new data points. We consider an application of this general framework for active learning the weight coefficients of a Gaussian radial basis function (RBF) network. We also derive some sufficiency conditions on the learning problem for which there are analytical solution to the data sampling procedure.
Active Learning by Sequential Optimal Recovery

In most classical frameworks for learning from examples, it is assumed that examples are randomly drawn and presented to the learner. In this paper, we consider the possibility of a more active learner who is allowed to choose his/her own examples. Our investigations are carried out in a function approximation setting. In particular, using arguments from optimal recovery (Micchelli and Rivlin, 1976), we develop an adaptive sampling strategy (equivalent to adaptive approximation) for arbitrary approximation schemes. We provide a general formulation of the problem and show how it can be regarded as sequential optimal recovery. We demonstrate the application of this general formulation to two special cases of functions on the real line 1) monotonically increasing functions and 2) functions with bounded derivative. An extensive investigation of the sample complexity of approximating these functions is conducted yielding both theoretical and empirical results on test functions. Our theoretical results (stated in PAC-style), along with the simulations demonstrate the superiority of our active scheme over both passive learning as well as classical optimal recovery. The analysis of active function approximation is conducted in a worst-case setting, in contrast with other Bayesian paradigms obtained from optimal design (Mackay,
Distributed Latent Variable Models of Lexical Co-occurrences

Low-dimensional representations for lexical co-occurrence data have become increasingly important in alleviating the sparse data problem inherent in natural language processing tasks. This work presents a distributed latent variable model for inducing these low-dimensional representations. The model takes inspiration from both connectionist language models [1, 16] and latent variable models [13, 9]. We give results which show that the new model significantly improves both bigram and trigram models.
Metric Learning by Collapsing Classes

We present an algorithm for learning a quadratic Gaussian metric (Mahalanobis distance) for use in classification tasks. Our method relies on the simple geometric intuition that a good metric is one under which points in the same class are simultaneously near each other and far from points in the other classes. We construct a convex optimization problem whose solution generates such a metric by trying to collapse all examples in the same class to a single point and push examples in other classes infinitely far away. We show that when the metric we learn is used in simple classifiers, it yields substantial improvements over standard alternatives on a variety of problems. We also discuss how the learned metric may be used to obtain a compact low dimensional feature representation of the original input space, allowing more efficient classification with very little reduction in performance.
Learning the Rules

Complex classifiers may exhibit "embarassing" failures in cases that would be easily classified and justified by a human. Avoiding such failures is obviously paramount, particularly in domains where we cannot accept this unexplained behavior. In this work, we focus on one such setting, where a label is perfectly predictable if the input contains certain features, and otherwise, it is predictable by a linear classifier. We define a related hypothesis class and determine its sample complexity. We also give evidence that efficient algorithms cannot, unfortunately, enjoy this sample complexity. We then derive a simple and efficient algorithm, and also give evidence that its sample complexity is optimal, among efficient algorithms. Experiments on sentiment analysis demonstrate the efficacy of the method, both in terms of accuracy and interpretability.
Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps.

We provide a framework for structural multiscale geometric organization of graphs and subsets of R(n). We use diffusion semigroups to generate multiscale geometries in order to organize and represent complex structures. We show that appropriately selected eigenfunctions or scaling functions of Markov matrices, which describe local transitions, lead to macroscopic descriptions at different scales. The process of iterating or diffusing the Markov matrix is seen as a generalization of some aspects of the Newtonian paradigm, in which local infinitesimal transitions of a system lead to global macroscopic descriptions by integration. We provide a unified view of ideas from data analysis, machine learning, and numerical analysis.
Geometric diffusions as a tool for harmonic analysis and structure definition of data: multiscale methods.

In the companion article, a framework for structural multiscale geometric organization of subsets of R(n) and of graphs was introduced. Here, diffusion semigroups are used to generate multiscale analyses in order to organize and represent complex structures. We emphasize the multiscale nature of these problems and build scaling functions of Markov matrices (describing local transitions) that lead to macroscopic descriptions at different scales. The process of iterating or diffusing the Markov matrix is seen as a generalization of some aspects of the Newtonian paradigm, in which local infinitesimal transitions of a system lead to global macroscopic descriptions by integration. This article deals with the construction of fast-order N algorithms for data representation and for homogenization of heterogeneous structures.
Langevin trajectories between fixed concentrations.

We consider the trajectories of particles diffusing between two infinite baths of fixed concentrations connected by a channel, e.g., a protein channel of a biological membrane. The steady state influx and efflux of Langevin trajectories at the boundaries of a finite volume containing the channel and parts of the two baths is replicated by termination of outgoing trajectories and injection according to a residual phase space density. We present a simulation scheme that maintains averaged fixed concentrations without creating spurious boundary layers, consistent with the assumed physics.
Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators

This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacency matrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density p(x) = e-U(x) we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential 2U(x) with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms.
Multiscale approach to ions in solution, proteins and channels: from brownian dynamics to continuum equations

for an Invited Paper for the MAR05 Meeting of The American Physical Society Multiscale approach to ions in solution, proteins and channels: from brownian dynamics to continuum equations BOAZ NADLER1, Department of Mathematics, Yale University The diffusive motion of ions in solution, near proteins and through protein channels of biological membranes involves many length and time scales. In this talk we’ll describe a multiscale averaging procedure, that starting from a Brownian dynamics description for the ionic motion of particles, yields a hierarchy of continuum equations for the averaged concentration profiles in the system. This set of equations is a generalization of the well known BBGKY equations of equilibrium statistical mechanics to non-equilibrium. Therefore, as in the equilibrium theory, closure relations are needed to compute explicit solutions. In the context of ionic permeation through protein channels, we show how an analysis of these continuum equations together with simple closures provides a theoretical explanation for experimentally measured phenomena. 1Joint work with R.S. Eisenberg and U. Hollerbach (Rush University, Chicago, IL) and Z. Schuss and A. Singer (Tel-Aviv University,
Uni-directional diffusion flux, Brownian and Langevin simulations

The Wiener path integral splits the net diffusion flux into infinite unidirectional fluxes, whose difference is the classical diffusion flux. The infinite unidirectional flux is an artifact of the diffusion approximation to Langevin’s equation, an approximation that fails on time scales shorter than the relaxation time 1/γ. The probability of one-dimensional Brownian trajectories that cross a point in one direction per unit time ∆t equals that of Langevin trajectories if γ∆t = 2. This result is relevant to Brownian and Langevin dynamics simulation of particles in a finite volume inside a large bath. We describe the sources of new trajectories at the boundaries of the simulation that maintain fixed average concentrations and avoid the formation of spurious boundary layers.
Unidirectional Flux In Brownian And Langevin Simulations Of Diffusion

Brownian and Langevin simulations of ions in solution require the maintenance of average fixed concentrations at the interface between the simulation volume and the surrounding continuum. This requires the injection of new trajectories into the simulation, which creates a unidirectional flux at the interface. The Wiener path integral splits the net diffusion flux into infinite unidirectional fluxes, whose difference is finite, as in classical diffusion theory. The infinite unidirectional flux is an artifact of the diffusion approximation to Langevin’s equation, which fails on time scales shorter than the relaxation time 1/γ. The probability of Brownian trajectories that cross a point in one direction per unit time Δt equals that of Langevin trajectories if γΔt = 2. This result is relevant to Brownian dynamics simulation of particles in a finite volume inside a large bath.
Randomized Sign Test for Dependent Observations on Discrete Choice under Risk

This paper proposes nonparametric statistical procedures for analyzing discrete choice models of affective decision making. We make two contributions to the literature on behavioral economics. Namely, we propose a procedure for eliciting the existence of a Nash equilibrium in an intrapersonal, potential game as well as randomized sign tests for dependent observations on game-theoretic models of affective decision making. This methodology is illustrated in the context of a hypothetical experiment -- the Casino Game.
Partial least squares, Beer's law and the net analyte signal: statistical modeling and analysis

Partial least squares (PLS) is one of the most common regression algorithms in chemistry, relating input–output samples (xi, yi) by a linear multivariate model. In this paper we analyze the PLS algorithm under a specific probabilistic model for the relation between x and y. Following Beer's law, we assume a linear mixture model in which each data sample (x, y) is a random realization from a joint probability distribution where x is the sum of k components multiplied by their respective characteristic responses, and each of these components is a random variable. We analyze PLS on this model under two idealized settings: one is the ideal case of noise‐free samples and the other is the case of an infinite number of noisy training samples. In the noise‐free case we prove that, as expected, the regression vector computed by PLS is, up to normalization, the net analyte signal. We prove that PLS computes this vector after at most k iterations, where k is the total number of components. In the case of an infinite training set corrupted by unstructured noise, we show that PLS computes a final regression vector which is not in general purely proportional to the net analyte signal vector, but has the important property of being optimal under a mean squared error of prediction criterion. This result can be viewed as an asymptotic optimality of PLS in the limit of a very large but finite training set.
The prediction error in CLS and PLS: the importance of feature selection prior to multivariate calibration

Classical least squares (CLS) and partial least squares (PLS) are two common multivariate regression algorithms in chemometrics. This paper presents an asymptotically exact mathematical analysis of the mean squared error of prediction of CLS and PLS under the linear mixture model commonly assumed in spectroscopy. For CLS regression with a very large calibration set the root mean squared error is approximately equal to the noise per wavelength divided by the length of the net analyte signal vector. It is shown, however, that for a finite training set with n samples in p dimensions there are additional error terms that depend on σ2p2/n2, where σ is the noise level per co‐ordinate. Therefore in the ‘large p—small n’ regime, common in spectroscopy, these terms can be quite large and even dominate the overall prediction error. It is demonstrated both theoretically and by simulations that dimensional reduction of the input data via their compact representation with a few features, selected for example by adaptive wavelet compression, can substantially decrease these effects and recover the asymptotic error. This analysis provides a theoretical justification for the need to perform feature selection (dimensional reduction) of the input data prior to application of multivariate regression algorithms.
Memoryless control of boundary concentrations of diffusing particles.

Flux between regions of different concentration occurs in nearly every device involving diffusion, whether an electrochemical cell, a bipolar transistor, or a protein channel in a biological membrane. Diffusion theory has calculated that flux since the time of Fick (1855), and the flux has been known to arise from the stochastic behavior of Brownian trajectories since the time of Einstein (1905), yet the mathematical description of the behavior of trajectories corresponding to different types of boundaries is not complete. We consider the trajectories of noninteracting particles diffusing in a finite region connecting two baths of fixed concentrations. Inside the region, the trajectories of diffusing particles are governed by the Langevin equation. To maintain average concentrations at the boundaries of the region at their values in the baths, a control mechanism is needed to set the boundary dynamics of the trajectories. Different control mechanisms are used in Langevin and Brownian simulations of such systems. We analyze models of controllers and derive equations for the time evolution and spatial distribution of particles inside the domain. Our analysis shows a distinct difference between the time evolution and the steady state concentrations. While the time evolution of the density is governed by an integral operator, the spatial distribution is governed by the familiar Fokker-Planck operator. The boundary conditions for the time dependent density depend on the model of the controller; however, this dependence disappears in the steady state, if the controller is of a renewal type. Renewal-type controllers, however, produce spurious boundary layers that can be catastrophic in simulations of charged particles, because even a tiny net charge can have global effects. The design of a nonrenewal controller that maintains concentrations of noninteracting particles without creating spurious boundary layers at the interface requires the solution of the time-dependent Fokker-Planck equation with absorption of outgoing trajectories and a source of ingoing trajectories on the boundary (the so called albedo problem).