Narrow Results

In the present paper we study the learnability of enumerable families ℒ of uniformly recursive languages in dependence on the number of allowed mind changes, i.e. with respect to a well-studied measure of efficiency.

We distinguish between exact learnability (ℒ has to be inferred w.r.t. ℒ) and class preserving learning (ℒ has to be inferred w.r.t. some suitable chosen enumeration of all the languages from ℒ) as well as between learning from positive and from both, positive and negative data.

The measure of efficiency is applied to prove the superiority of class preserving learning algorithms over exact learning. In particular, we considerably improve results obtained previously and establish two infinite hierarchies. Furthermore, we separate exact and class preserving learning from positive data that avoids overgeneralization. Finally, language learning with a bounded number of mind changes is completely characterized in terms of recursively generable finite sets. These characterizations offer a new method to handle overgeneralizations and resolve an open question of Mukouchi.¹

In previous contributions we presented a new class of algorithms for orthonormal learning of a linear neural network with p inputs and m outputs, based on the equations describing the dynamics of a massive rigid frame in a submanifold of ℛ^p. While exhibiting interesting features, such as intrinsic numerical stability, strongly binding to the orthonormal submanifolds, and good controllability of the learning dynamics, tested on principal/independent component analysis, the proposed algorithms were not completely satisfactory from a computational-complexity point of view. The main drawback was the need to repeatedly evaluate a matrix exponential map. With the aim to lessen the computational efforts pertaining to these algorithms, we propose here an improvement based on the closed-form Rodriguez formula for the exponential map. Such formula is available in the p=3 and m=3 case, which is discussed with details here. In particular, experimental results on independent component analysis (ICA), carried out with both synthetic and real-world data, help confirming the computational gain due to the proposed improvement.

The aim of this manuscript is to present a detailed analysis of the algebraic and geometric properties of relative uncertainty theory (RUT) applied to neural networks learning. Through the algebraic analysis of the original learning criterion, it is shown that RUT gives rise to principal-subspace-analysis-type learning equations. Through an algebraic-geometric analysis, the behavior of such matrix-type learning equations is illustrated, with particular emphasis to the existence of certain invariant manifolds.

The present manuscript aims at illustrating fundamental challenges and solutions arising in the design of learning theories by optimization on manifolds in the context of complex-valued neural systems. The special case of a unitary unimodular group of matrices is dealt with. The unitary unimodular group under analysis is a low dimensional and easy-to-handle matrix group. Notwithstanding, it exhibits a rich geometrical structure and gives rise to interesting speculations about methods to solve optimization problems on manifolds. Also, its low dimension allows us to treat most of the quantities involved in computation in closed form as well as to render them in graphical format. Some numerical experiments are presented and discussed within the paper, which deal with complex-valued independent component analysis.

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 L₂ 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 this paper, we address learning rates for the density level detection (DLD) problem. We begin by proving a "No Free Lunch Theorem" showing that rates cannot be obtained in general. Then, we apply a recently established classification framework to obtain rates for DLD support vector machines under mild assumptions on the density.

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 (x_t, y_t) 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 learning algorithms induced by regularization methods in the regression setting. We show that previously obtained error bounds for these algorithms, using a priori choices of the regularization parameter, can be attained using a suitable a posteriori choice based on cross-validation. In particular, these results prove adaptation of the rate of convergence of the estimators to the minimax rate induced by the "effective dimension" of the problem. We also show universal consistency for this broad class of methods which includes regularized least-squares, truncated SVD, Landweber iteration and ν-method.

We consider a wide class of error bounds developed in the context of statistical learning theory which are expressed in terms of functionals of the regression function, for instance, its norm in a reproducing kernel Hilbert space or other functional space. These bounds are unstable in the sense that a small perturbation of the regression function can induce an arbitrary large increase of the relevant functional and make the error bound useless. Using a known result involving Fano inequality, we show how stability can be recovered.

We introduce a learning algorithm for regression generated by a minimum error entropy (MEE) principle and regularization schemes in reproducing kernel Hilbert spaces. This empirical MEE algorithm is highly related to a scaling parameter arising from Parzen windowing. The purpose of this paper is to carry out consistency analysis when the scaling parameter is large. Explicit learning rates are provided. Novel approaches are proposed to overcome the difficulties in bounding the output function uniformly and in the special MEE feature that the regression function may not be a minimizer of the error entropy.

Spectral algorithms form a general framework that unifies many regularization schemes in learning theory. In this paper, we propose and analyze a class of thresholded spectral algorithms that are designed based on empirical features. Soft thresholding is adopted to achieve sparse approximations. Our analysis shows that without sparsity assumption of the regression function, the output functions of thresholded spectral algorithms are represented by empirical features with satisfactory sparsity, and the convergence rates are comparable to those of the classical spectral algorithms in the literature.

Based on the tree architecture, the objective of this paper is to design deep neural networks with two or more hidden layers (called deep nets) for realization of radial functions so as to enable rotational invariance for near-optimal function approximation in an arbitrarily high-dimensional Euclidian space. It is shown that deep nets have much better performance than shallow nets (with only one hidden layer) in terms of approximation accuracy and learning capabilities. In particular, for learning radial functions, it is shown that near-optimal rate can be achieved by deep nets but not by shallow nets. Our results illustrate the necessity of depth in neural network design for realization of rotation-invariance target functions.

$K$-functionals are used in learning theory literature to study approximation errors in kernel-based regularization schemes. In this paper, we study the approximation error and $K$-functionals in $L^p$ spaces with $p\ge 1$. To this end, we give a new viewpoint for a reproducing kernel Hilbert space (RKHS) from a fractional derivative and treat powers of the induced integral operator as fractional derivatives of various orders. Then a generalized translation operator is defined by Fourier multipliers, with which a generalized modulus of smoothness is defined. Some general strong equivalent relations between the moduli of smoothness and the $K$-functionals are established. As applications, some strong equivalent relations between these two families of quantities on the unit sphere and the unit ball are provided explicitly.

This paper proposes a novel prediction approach for a semi-functional linear model comprising a functional and a nonparametric component. The study establishes the minimax optimal rates of convergence for this model, revealing that the functional component can be learned with the same minimax rate as if the nonparametric component were known and vice versa. This result can be achieved by using a double-penalized least squares method to estimate both the functional and nonparametric components within the framework of reproducing kernel Hilbert spaces. Thanks to the representer theorem, the approach also offers other desirable features, including the algorithm efficiency requiring no iterations. We also provide numerical studies to demonstrate the effectiveness of the method and validate the theoretical analysis.

We give investigations on a kernel function approximation problem arising from learning theory and show the convergence rate from the view of classical Fourier analysis. First, we provide the general definition for a modulus of smoothness and a $K$-functional, and show that they are equivalent. In particular, we give explicit representation for some moduli of smoothness. Second, we establish some Jackson-type inequalities for the approximation error associated with some non-radial kernels. Also we apply these results to some concrete classical kernel function spaces and give Jackson-type inequalities for some concrete RKHS approximation problems. Finally, we apply these discussions to learning theory and describe the learning rates with the moduli of smoothness. The tools we used are Fourier analysis and the semigroup operator. The results show that the Jackson-type inequalities of approximation by some radial kernel functions on compact set with nonempty interiors cannot be expressed with the classical moduli of smoothness.

The study of regularized learning algorithms is a very important issue and functional data analysis extends classical methods. We establish the learning rates of the least square regularized regression algorithm in reproducing kernel Hilbert space for functional data. With the iteration method, we obtain fast learning rate for functional data. Our result is a natural extension for least square regularized regression algorithm when the dimension of input data is finite.

In this paper, we investigate coefficient-based regularized least squares regression problem in a data dependent hypothesis space. The learning algorithm is implemented with samples drawn by unbounded sampling processes and the error analysis is performed by a stepping-stone technique. A new error decomposition technique is proposed for the error analysis. The regularization parameters in our setting provide much more flexibility and adaptivity. Sharp learning rates are addressed by means of l²-empirical covering numbers under a moment hypothesis condition.

In this paper, we consider conditional quantile regression learning algorithms based on the pinball loss with data dependent hypothesis space and ℓ²-regularizer. Functions in this hypothesis space are linear combination of basis functions generated by a kernel function and sample data. The only conditions imposed on the kernel function are the continuity and boundedness which are pretty weak. Our main goal is to study the consistency of this regularized quantile regression learning. By concentration inequality with ℓ²-empirical covering numbers and operator decomposition techniques, satisfied error bounds and convergence rates are explicitly derived.

In this paper, the regression learning algorithm with vector-valued RKHS is studied. We motivate the need for extending learning theory of scalar-valued functions and analze the learning performance. In this setting, the output data are from a Hilbert space $Y$, the associated RKHS consists of functions with values lie in $Y$. By providing mathematical aspects of vector-valued integral operator $L_K$, the capacity independent error bounds and learning rates are derived by means of the integral operator technique.

In this paper, we study the performance of kernel-based regression learning with non-iid sampling. The non-iid samples are drawn from different probability distributions with the same conditional distribution. A more general marginal distribution assumption is proposed. Under this assumption, the consistency of the regularization kernel network (RKN) and the coefficient regularization kernel network (CRKN) are proved. Satisfactory capacity independently error bounds and learning rates are derived by the techniques of integral operator.