共查询到20条相似文献,搜索用时 31 毫秒
1.
One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed (i.i.d.) samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization (ERM) algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain samples is consistent. The established theory underlies application of ERM type of learning algorithms. 相似文献
2.
The previous results describing the generalization ability of Empirical Risk Minimization (ERM) algorithm are usually based
on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical
framework by establishing the first exponential bound on the rate of uniform convergence of the ERM algorithm with V-geometrically ergodic Markov chain samples, as the application of the bound on the rate of uniform convergence, we also obtain
the generalization bounds of the ERM algorithm with V-geometrically ergodic Markov chain samples and prove that the ERM algorithm with V-geometrically ergodic Markov chain samples is consistent. The main results obtained in this paper extend the previously known
results of i.i.d. observations to the case of V-geometrically ergodic Markov chain samples. 相似文献
3.
New Bernstein's Inequalities for Dependent Observations and Applications to Learning Theory
下载免费PDF全文
![点击此处可从《应用概率统计》网站下载免费的PDF全文](/ch/ext_images/free.gif)
The classical concentration inequalities deal with the deviations
of functions of independent and identically distributed (i.i.d.) random variables from their
expectation and these inequalities have numerous important applications in statistics and
machine learning theory. In this paper we go far beyond this classical framework by establish
two new Bernstein type concentration inequalities for -mixing sequence and uniformly
ergodic Markov chains. As the applications of the Bernstein's inequalities, we also obtain
the bounds on the rate of uniform deviations of empirical risk minimization (ERM) algorithms
based on -mixing observations. 相似文献
4.
Bin Zou Luoqing Li Zongben Xu 《Journal of Mathematical Analysis and Applications》2012,388(1):333-343
The previously known works describing the generalization of least-square regularized regression algorithm are usually based on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by studying the generalization of least-square regularized regression algorithm with Markov chain samples. We first establish a novel concentration inequality for uniformly ergodic Markov chains, then we establish the bounds on the generalization of least-square regularized regression algorithm with uniformly ergodic Markov chain samples, and show that least-square regularized regression algorithm with uniformly ergodic Markov chains is consistent. 相似文献
5.
6.
7.
8.
Online gradient method has been widely used as a learning algorithm for training feedforward neural networks. Penalty is often introduced into the training procedure to improve the generalization performance and to decrease the magnitude of network weights. In this paper, some weight boundedness and deterministic con- vergence theorems are proved for the online gradient method with penalty for BP neural network with a hidden layer, assuming that the training samples are supplied with the network in a fixed order within each epoch. The monotonicity of the error function with penalty is also guaranteed in the training iteration. Simulation results for a 3-bits parity problem are presented to support our theoretical results. 相似文献
9.
Evaluation for the performance of learning algorithm has been the main thread of theoretical research of machine learning.
The performance of the regularized regression algorithm based on independent and identically distributed(i.i.d.) samples has
been researched by a large number of references. In the present paper we provide the convergence rates for the performance
of regularized regression based on the inputs of p-order Markov chains. 相似文献
10.
基于代数等价路径的一致P-函数非线性互补问题的可行内点算法 总被引:2,自引:0,他引:2
对一致P-函数非线性互补问题,提出了一种新的基于代数等价路径的可行内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛;当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,特别对于单调线性互补问题,总迭代次数为O(√nL),其中L是问题的输入长度。 相似文献
11.
In this paper constrained LQR problems in distributed control systems governed by the elliptic equation with point observations
are studied. A variational inequality approach coupled with potential theory in a Banach space setting is adopted. First the
admissible control set is extended to be bounded by two functions, and feedback characterization of the optimal control in
terms of the optimal state is derived; then two numerical algorithms proposed in [5] are modified, and the strong convergence
and uniform convergence in Banach space are proved. This verifies that the numerical algorithm is insensitive to the partition
number of the boundary. Since our control variables are truncated below and above by two functions inL
p and in our numerical computation only the layer density not the control variable is assumed to be piecewise smooth, uniform
convergence guarantees a better convergence. Finally numerical computation for an example is carried out and confirms the
analysis.
This research was supported in part by NSF Grant DMS-9404380 and by an IRI Award of Texas A&M University. The current address
of the first author is the Department of Mathematical Science, University of Nevada at Las Vegas, Las Vegas, NV 89154, USA. 相似文献
12.
Sayan Mukherjee Partha Niyogi Tomaso Poggio Ryan Rifkin 《Advances in Computational Mathematics》2006,25(1-3):161-193
Solutions of learning problems by Empirical Risk Minimization (ERM) – and almost-ERM when the minimizer does not exist – need
to be consistent, so that they may be predictive. They also need to be well-posed in the sense of being stable, so that they might be used robustly. We propose a statistical form of stability, defined as leave-one-out (LOO) stability. We prove that for bounded loss classes LOO stability is (a) sufficient for generalization, that is convergence in probability of the empirical error to the expected error, for any algorithm satisfying it and, (b)
necessary and sufficient for consistency of ERM. Thus LOO stability is a weak form of stability that represents a sufficient condition for generalization for symmetric learning
algorithms while subsuming the classical conditions for consistency of ERM. In particular, we conclude that a certain form
of well-posedness and consistency are equivalent for ERM.
Dedicated to Charles A. Micchelli on his 60th birthday
Mathematics subject classifications (2000) 68T05, 68T10, 68Q32, 62M20.
Tomaso Poggio: Corresponding author. 相似文献
13.
介绍模糊粗糙理论的基本内容;提出模糊粗糙经验风险泛函,模糊粗糙期望风险泛函,模糊粗糙经验风险最小化原则等概念;最后证明基于模糊粗糙样本的统计学习理论的关键定理并构建学习过程一致收敛速度的界. 相似文献
14.
15.
Huanhuan Cui 《Optimization》2017,66(5):793-809
The proximal point algorithm (PPA) is a classical method for finding zeros of maximal monotone operators. It is known that the algorithm only has weak convergence in a general Hilbert space. Recently, Wang, Wang and Xu proposed two modifications of the PPA and established strong convergence theorems on these two algorithms. However, these two convergence theorems exclude an important case, namely, the over-relaxed case. In this paper, we extend the above convergence theorems from under-relaxed case to the over-relaxed case, which in turn improve the performance of these two algorithms. Preliminary numerical experiments show that the algorithm with over-relaxed parameter performs better than that with under-relaxed parameter. 相似文献
16.
基于模糊随机样本空间,提出了模糊随机期望风险泛函,模糊随机经验风险泛函和模糊随机经验风险泛函最小化原则等概念;基于模糊随机变量及其期望,讨论了相关概率不等式;最后证明了基于模糊随机样本统计学习理论的关键定理并研究了学习过程一致收敛速度的界等问题. 相似文献
17.
Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced. 相似文献
18.
Mehrotra's predictor-corrector algorithm [3] is currently considered to be one of the most practically efficient interior-point methods for linear programming. Recently, Zhang and Zhang [18] studied the global convergence properties of the Mehrotra-type predictor-corrector approach and established polynomial complexity bounds for two interior-point algorithms that use the Mehrotra predictor-corrector approach. In this paper, we study the asymptotic convergence rate for the Mehrotra-type predictor-corrector interior-point algorithms. In particular, we construct an infeasible-interior-point algorithm based on the second algorithm proposed in [18] and show that while retaining a complexity bound ofO(n
1.5
t)-iterations, under certain conditions the algorithm also possesses aQ-subquadratic convergence, i.e., a convergence ofQ-order 2 with an unboundedQ-factor.Research supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171. 相似文献
19.
New approaches to statistical learning theory 总被引:3,自引:0,他引:3
Olivier Bousquet 《Annals of the Institute of Statistical Mathematics》2003,55(2):371-389
We present new tools from probability theory that can be applied to the analysis of learning algorithms. These tools allow
to derive new bounds on the generalization performance of learning algorithms and to propose alternative measures of the complexity
of the learning task, which in turn can be used to derive new learning algorithms. 相似文献
20.
Jean-Yves Audibert 《Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques》2004,40(6):148-736
Numerous empirical results have shown that combining regression procedures can be a very efficient method. This work provides PAC bounds for the L2 generalization error of such methods. The interest of these bounds are twofold.First, it gives for any aggregating procedure a bound for the expected risk depending on the empirical risk and the empirical complexity measured by the Kullback–Leibler divergence between the aggregating distribution
and a prior distribution π and by the empirical mean of the variance of the regression functions under the probability
.Secondly, by structural risk minimization, we derive an aggregating procedure which takes advantage of the unknown properties of the best mixture
: when the best convex combination
of d regression functions belongs to the d initial functions (i.e. when combining does not make the bias decrease), the convergence rate is of order (logd)/N. In the worst case, our combining procedure achieves a convergence rate of order
which is known to be optimal in a uniform sense when
(see [A. Nemirovski, in: Probability Summer School, Saint Flour, 1998; Y. Yang, Aggregating regression procedures for a better performance, 2001]).As in AdaBoost, our aggregating distribution tends to favor functions which disagree with the mixture on mispredicted points. Our algorithm is tested on artificial classification data (which have been also used for testing other boosting methods, such as AdaBoost). 相似文献