Search

This paper attempts to give an extension of learning theory to a setting where the assumption of i.i.d. data is weakened by keeping the independence but abandoning the identical restriction. We hypothesize that a sequence of examples (xt, yt) in X × Y for t = 1, 2, 3,… is drawn from a probability distribution ρt on X × Y. The marginal probabilities on X are supposed to converge to a limit probability on X. Two main examples for this time process are discussed. The first is a stochastic one which in the special case of a finite space X is defined by a stochastic matrix and more generally by a stochastic kernel. The second is determined by an underlying discrete dynamical system on the space X. Our theoretical treatment requires that this dynamics be hyperbolic (or "Axiom A") which still permits a class of chaotic systems (with Sinai–Ruelle–Bowen attractors). Even in the case of a limit Dirac point probability, one needs the measure theory to be defined using Hölder spaces. Many implications of our work remain unexplored. These include, for example, the relation to Hidden Markov Models, as well as Markov Chain Monte Carlo methods. It seems reasonable that further work should consider the push forward of the process from X × Y by some kind of observable function to a data space.

We consider the regression problem and describe an algorithm approximating the regression function by estimators piecewise constant on the elements of an adaptive partition. The partitions are iteratively constructed by suitable random merges and splits, using cuts of arbitrary geometry. We give a risk bound under the assumption that a "weak learning hypothesis" holds, and characterize this hypothesis in terms of a suitable RKHS. Two examples illustrate the general results in two particularly interesting cases.

The regression problem in learning theory is investigated with least square Tikhonov regularization schemes in reproducing kernel Hilbert spaces (RKHS). We follow our previous work and apply the sampling operator to the error analysis in both the RKHS norm and the L2 norm. The tool for estimating the sample error is a Bennet inequality for random variables with values in Hilbert spaces. By taking the Hilbert space to be the one consisting of Hilbert-Schmidt operators in the RKHS, we improve the error bounds in the L2 metric, motivated by an idea of Caponnetto and de Vito. The error bounds we derive in the RKHS norm, together with a Tsybakov function we discuss here, yield interesting applications to the error analysis of the (binary) classification problem, since the RKHS metric controls the one for the uniform convergence.

We continue our study [S. Smale, D.X. Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc. 41 (2004) 279–305] of Shannon sampling and function reconstruction. In this paper, the error analysis is improved. Then we show how our approach can be applied to learning theory: a functional analysis framework is presented; dimension independent probability estimates are given not only for the error in the L 2 spaces, but also for the error in the reproducing kernel Hilbert space where the learning algorithm is performed. Covering number arguments are replaced by estimates of integral operators.

Let B be a Banach space and (ℋ,‖·‖ℋ) be a dense, imbedded subspace. For a ∈ B, its distance to the ball of ℋ with radius R (denoted as I(a, R)) tends to zero when R tends to infinity. We are interested in the rate of this convergence. This approximation problem arose from the study of learning theory, where B is the L2 space and ℋ is a reproducing kernel Hilbert space. The class of elements having I(a, R) = O(R-r) with r > 0 is an interpolation space of the couple (B, ℋ). The rate of convergence can often be realized by linear operators. In particular, this is the case when ℋ is the range of a compact, symmetric, and strictly positive definite linear operator on a separable Hilbert space B. For the kernel approximation studied in Learning Theory, the rate depends on the regularity of the kernel function. This yields error estimates for the approximation by reproducing kernel Hilbert spaces. When the kernel is smooth, the convergence is slow and a logarithmic convergence rate is presented for analytic kernels in this paper. The purpose of our results is to provide some theoretical estimates, including the constants, for the approximation error required for the learning theory.

In Part I (Chapters 2 and 3) we introduced finite-dimensional machines with inputs from R n for some n ∈ ℕ and (uniform) machines whose inputs are from R n for all n ∈ ℕ. On the other hand, one can imagine a machine where inputs are taken from R ∞ but where the program to be executed depends on the size of the given input. The simplest example of such a machine is a family of finite-dimensional machines containing one machine for each input dimension. These machines are called nonuniform.

Although it may not be at all obvious given a polynomial over R how to decide whether it has a zero over R, it is a straightforward procedure to verify a solution that may be presented to us. Just plug the purported solution into the polynomial and evaluate it. Is this verification tractable in our model of computation? An affirmative answer will depend on the underlying mathematical properties of the ring or field, as well as our measure of complexity, and is at the core of the notion of NP.

Classical complexity theory deals primarily with combinatorial (discrete, integer) problems. We extend the theory here to consider a wider class of problems.

In this paper we study volume estimates in the space of systems of n homegeneous polynomial equations of fixed degrees d i with respect to a natural Hermitian structure on the space of such systems invariant under the action of the unitary group. We show that the average number of real roots of real systems is D 1/2 where D = Π d i is the Be zout number. We estimate the volume of the subspace of badly conditioned problems and show that volume is bounded by a small degree polynomial in n, N and D times the reciprocal of the condition number to the fourth power. Here N is the dimension of the space of systems.

We show that there are algorithms which find an approximate zero of a system of polynomial equations and which function in polynomial time on the average. The number of arithmetic operations is cN4s, where N is the input size and c a universal constant.

Here we describe a mathematical model in the field of cellular biology. It is a model for two similar cells which interact via diffusion past a membrane. Each cell by itself is inert or dead in the sense that the concentrations of its enzymes achieve a constant equilibrium. In interaction however, the cellular system pulses (or expressed perhaps over dramatically, becomes alive!) in the sense that the concentrations of the enzymes in each cell will oscillate indefinitely. Of course we are using an extremely simplified picture of actual cells.

A model for computation over an arbitrary (ordered) ring R is presented. In this general setting, universal machines, partial recursive functions, and NP-complete problems are obtained. While the theory reflects of classical over Z (e.g. the computable functions are the recursive functions), it also reflects the special mathematical character of the underlying ring R (e.g. complements of Julia sets provide natural examples of recursively enumerable undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis. >

Publisher Summary This chapter discusses that every diffeomorphism of a compact manifold is differentiably isotopic to one that is Ω-stable as a discrete dynamical system. It discusses a theorem that every diffeomorphism of a compact manifold is differentiably isotopic to one satisfying Axiom A and the no-cycle condition and corollary that every diffeomorphism is differentiably isotopic to an instable one. The theorem is reminiscent of the theorem that every manifold supports a structurally stable vector field, that is, continuous dynamical system. In the case discussed in the chapter, however, the dynamical system obtained must be more complicated, as the Lefschetz trace formula implies, even for many isotopy classes on 2-manifolds, that there are an infinite number of periodic orbits.

We show that the integer roots of of a univariate polynomial with integer coefficients can be computed in polynomial time. This result holds for the classical (i.e. Turing) model of computation and a sparse representation of polynomials (i.e. coefficients and exponents are written in binary, and only nonzero monomials are represented)., On montre que les racines entières d'un polynôme en une variable à coefficients entiers peuvent être calculées en temps polynomial. Ce résultat est valable pour le modèle de calcul classique des machines de Turing et pour une représentation creuse des polynômes (coefficients et exposants sont écrits en binaire, et seuls les monômes non nul sont représentés).