文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Rigorous learning curve bounds from statistical mechanics
侵权投诉

Rigorous learning curve bounds from statistical mechanics

In this paper we introduce and investigate a mathematically rigorous theory of learning curves that is based on ideas from statistical mechanics. The advantage of our theory over the well-established Vapnik-Chervonenkis theory is that our bounds can be con

Rigorous Learning Curve Bounds from Statistical Mechanics David Haussler U.C. Santa Cruz Santa Cruz, California H. Sebastian Seung AT&T Bell Laboratories Murray Hill, New Jersey Abstract In this paper we introduce and investigate a mathematically rigorous theory of learning curves that is based on ideas from statistical mechanics. The advantage of our theory over the well-established Vapnik-Chervonenkis theory is that our bounds can be considerably tighter in many cases, and are also more re ective of the true behavior (functional form) of learning curves. This behavior can often exhibit dramatic properties such as phase transitions, as well as power law asymptotics not explained by the VC theory. The disadvantages of our theory are that its application requires knowledge of the input distribution, and it is limited so far to nite cardinality function classes. We illustrate our results with many concrete examples of learning curve bounds derived from our theory. 1 Introduction According to the Vapnik-Chervonenkis (VC) theory of learning curves 31, 30], minimizing empirical error within a function class F on a random sample of m examples leads to~ generalization error bounded by O (d=m) (in the case that~p the target function is contained in F ) or O ( d=m) plus the optimal generalization error achievable within F (in the general case). 1 These bounds are universal: they hold for any class of hypothesis functions F, for any input distribution, and for any target function. The only problem-speci c quantity remaining in these bounds is the VC dimension d, a measure of the complexity of the function class F . It has been shown that these bounds are essentially the best distribution-independent bounds possible, in the sense that for any function class, there exists an input distribution for which matching lower bounds on the generalization error can be given 6, 8, 26]. The universal VC bounds can give the impression that the true behavior of learning curves is also universal, p esand sentially described by the functional forms d=m and d=m. 1 Here for simplicity we are using the O( ) notation, which hides~ logarithmic factors in the same way the O( ) notation hides constant factors.

Michael Kearns AT&T Bell Laboratories Murray Hill, New Jersey Naftali Tishby Hebrew University Jerusalem, Israel However, it is becoming clear that learning curves exhibit a diversity of behaviors. For instance, some researchers have attempted to t learning curves from backpropagation experiments with a variety of functional forms, including exponentials 4]. Backpropagation experiments with handwritten digits and characters indicate that good generalization error is sometimes obtained for sample sizes considerably smaller than the number of weights (presumed to be roughly the same as the VC dimension) 20], though the VC bounds are vacuous for m smaller than d. Discrepancies between the VC bounds and actual learning curve behavior have also been pointed out and analyzed

in other machine learning work 23, 21]. Of course, the VC bounds might simply be inapplicable to these experiments, because backpropagation is not equivalent to empirical error minimization. Vapnik has conjectured that backpropagation can access only a limited portion of the function space, so that the\e ective dimension" is much smaller than the VC dimension. According to this type of reasoning, learning curves are heavily a ected by the speci cs of the algorithm. Another possibility is that the VC bounds are applicable, but sometimes fail to capture the true behavior of particular learning curves because of their independence from the distribution. Hence some theorists have sought to preserve the functional form of the VC bounds, but to replace the VC dimension in this functional form by an appropriate distribution-speci c quantity, such as the VC entropy (which is the expectation of the logarithm of the number of dichotomies realized by the function class) 30, 17, 3]. Work on the\empirical VC dimension" has tried to measure the dependence of learning curves on both the algorithm and the distribution via backpropagation experiments 29]. Perhaps the most striking evidence for the fact that the VC bounds can sometimes fail to model the true behavior of learning curves has come from statistical physics. In recent years, the tools of statistical mechanics have been applied to analyze learning curves with rather curious and dramatic behavior (See the survey of Watkin, Rau and Biehl and the references therein 32]). This has included learning curves exhibiting\phase transitions" (sudden drops in the generalization error) at small sample sizes, as well as asymptotic power law behavior 2 in which the power law exponent is neither 1 nor 1/2. Although these learning curves do not contradict the VC bounds, it seems fair to say that their behavior is qualitatively di erent. The theoretical revisions of the VC theory mentioned above cannot explain such be-

2 By a power law, we mean the functional form (a=m)b, where a; b> 0 are constants.

第1页

你可能喜欢

热门文档

相关文档

  • Bounds for predictive errors in the statistical mec...

    Rigorous learning curve ... 暂无评价 42页 免费 Rigorous learning curve .....Bounds for predictive errors in the statistical mechanics of supervised learning...

  • Statistical Bounds on Equity

    Rigorous learning curve ... 暂无评价 20页 免费 Bounds for predictive er.....Those who know statistical mechanics will ?nd a very close resemblance with...

  • Statistical Bounds on Equity

    Rigorous learning curve ... 暂无评价 20页 免费 Bounds for predictive er.....Those who know statistical mechanics will ?nd a very close resemblance with...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email