CiteULike: sdvillal's Ben-David

Scale-sensitive dimensions, uniform convergence, and learnability

Noga Alon — 2008-04-30T12:29:38-00:00

J. ACM, Vol. 44, No. 4. (July 1997), pp. 615-631.

Alternative Measures of Computational Complexity with Applications to Agnostic Learning

Shai Ben-David — 2008-03-28T10:27:57-00:00

Theory and Applications of Models of Computation (2006), pp. 231-235.

We address a fundamental problem of complexity theory - the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best known measure and enjoying the support of a rich and elegant theory, worst-case complexity seems gives rise to over-pessimistic complexity values. Many standard task, that are being carried out routinely in machine learning applications, are NP-hard, that is, infeasible from the worst-case-complexity perspective. In this work we offer an alternative measure of complexity for approximations-optimization tasks. Our approach is to define a hierarchy on the set of inputs to a learning task, so that natural ('real data') inputs occupy only bounded levels of this hierarchy and that there are algorithms that handle in polynomial time each such bounded level.

Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher

Shai Ben-David — 2007-03-08T17:51:20-00:00

Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 171-182.

We propose a mathematical model for learning the high-density areas of an unknown distribution from (unlabeled) random points drawn according to this distribution. While this type of a learning task has not been previously addressed in the computational learnability literature, we believe that this it a rather basic problem that appears in many practical learning scenarios. From a statistical theory standpoint, our model may be viewed as a restricted instance of the fundamental issue of inferring information about a probability distribution from the random samples it generates. From a computational learning angle, what we propose is a few framework of unsupervised concept learning. The examples provided to the learner in our model are not labeled (and are not necessarily all positive or all negative). The only information about their membership is indirectly disclosed to the student through the sampling distribution. We investigate the basic features of the proposed model and provide lower and upper bounds on the sample complexity of such learning tasks. We prove that classes whose VC-dimension is finite are learnable in a very strong sense, while on the other hand,[var epsilon]-covering numbers of a concept class impose lower bounds on the sample size needed for learning in our models. One direction of the proof involves a reduction of the density-level learnability to PAC learning with respect to fixed distributions (as well as some fundamental statistical lower bounds), while the sufficiency condition is proved through the introduction of a generic learning algorithm.