检索结果-内蒙古大学图书馆

18th international conference on algorithmic learning theory

作者： Tirnauca, Cristina Knuutila, Timo Univ Rovira & Virgili Res Grp Math Linguist Pl Imperial Tarraco 1 Tarragona 43005 Spain Turku Univ Dept Informat Technol FI-20014 Turku Finland

ISBN: (纸本)9783540752240

We investigate two of the language classes intensively studied by the algorithmic learning theory community in the context of learning with correction queries. More precisely, we show that any pattern language can be inferred in polynomial time in length of the pattern by asking just a linear number of correction queries, and that k-reversible languages are efficiently learnable within this setting. Note that although the class of all pattern languages is learnable with membership queries, this cannot be done in polynomial time. Moreover, the class of k-reversible languages is not learnable at all using membership queries only.

关键词： correction queries k-reversible languages pattern languages polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiple pass streaming algorithms for learning mixtures of distributions in R^d

引用

thEORETICAL COMPUTER SCIENCE 2009年第19期410卷 1765-1780页

作者： Chang, Kevin L. Yahool Inc Yahool Labs Sunnyvale CA 94089 USA

We present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in R-d, for any d > 0. Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2l + 2 passes, for any l > 0, and requires memory at most (O) over tilde(epsilon(-2/l) k(2)d(4) + (4k)(d)), where E is the tolerable error of the algorithm. this exhibits a strong memory-pass tradeoff in terms of E: a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Karman first considered this problem for of d = 1, 2. Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Streaming algorithm Machine learning Mixture model Computational learning theory

来源：评论

学校读者我要写书评

暂无评论

learning rational Stochastic tree languages

Learning rational Stochastic tree languages

引用

18th international conference on algorithmic learning theory

作者： Denis, Francois Habrard, Amaury Aix Marseille Univ CNRS Lab Informat Fondamentale Marseille Marseille France

ISBN: (纸本)9783540752240

We consider the problem of learning stochastic tree languages, i.e. probability distributions over a set of trees T(F), from a sample of trees independently drawn according to an unknown target P. We consider the case where the target is a rational stochastic tree language, i.e. it can be computed by a rational tree series or, equivalently, by a multiplicity tree automaton. In this paper, we provide two contributions. First, we show that rational tree series admit a canonical representation with parameters that can be efficiently estimated from samples. then, we give an inference algorithm that identifies the class of rational stochastic tree languages in the limit with probability one.

关键词： learning systems

来源：评论

学校读者我要写书评

暂无评论

Online regression competitive with changing predictors

Online regression competitive with changing predictors

引用

18th international conference on algorithmic learning theory

作者： Busuttil, Steven Kalnishkan, Yuri Royal Holloway Univ London Comp Learning Res Ctr Egham TW20 0EX Surrey England

ISBN: (纸本)9783540752240

this paper deals with the problem of making predictions in the online mode of learning where the dependence of the outcome y(t) on the signal x(t) can change with time. the Aggregating Algorithm (AA) is a technique that optimally merges experts from a pool, so that the resulting strategy suffers a cumulative loss that is almost as good as that of the best expert in the pool. We apply the AA to the case where the experts are all the linear predictors that can change with time. KAARCh is the kernel version of the resulting algorithm. In the kernel case, the experts are all the decision rules in some reproducing kernel Hilbert space that can change over time. We show that KAARCh suffers a cumulative square loss that is almost as good as that of any expert that does not change very rapidly.

关键词： Online systems

来源：评论

学校读者我要写书评

暂无评论

learning kernel Perceptrons on noisy data using random projections

Learning kernel Perceptrons on noisy data using random proje...

引用

18th international conference on algorithmic learning theory

作者： Stempfel, Guillaume Ralaivola, Liva Univ Aix Marseille 1 CNRS Lab Informat Fondamentale Marseille UMR 6166 39 Rue Joliot Curie F-13013 Marseille France

ISBN: (纸本)9783540752240

In this paper, we address the issue of learning nonlinearly separable concepts with a kernel classifier in the situation where the data at hand are altered by a uniform classification noise. Our proposed approach relies on the combination of the technique of random or deterministic projections with a classification noise tolerant perceptron learning algorithm that assumes distributions defined over finite-dimensional spaces. Provided a sufficient separation margin characterizes the problem, this strategy makes it possible to envision the learning from a noisy distribution in any separable Hilbert space, regardless of its dimension;learning with any appropriate Mercer kernel is therefore possible. We prove that the required sample complexity and running time of our algorithm is polynomial in the classical PAC learning parameters. Numerical simulations on toy datasets and on data from the UCI repository support the validity of our approach.

关键词： learning systems

来源：评论

学校读者我要写书评

暂无评论

learning in Friedberg numberings

Learning in Friedberg numberings

引用

18th international conference on algorithmic learning theory

作者： Jain, Sanjay Stephan, Frank Natl Univ Singapore Dept Comp Sci Singapore 117590 Singapore Natl Univ Singapore Dept Math Singapore 117548 Singapore

ISBN: (纸本)9783540752240

In this paper we consider learnability in some special numberings, such as Friedberg numberings, which contain all the recursively enumerable languages, but have simpler grammar equivalence problem compared to acceptable numberings. We show that every explanatorily learnable class can be learnt in some Friedberg numbering. However, such a result does not hold for behaviourally correct learning or finite learning. One can also show that some Friedberg numberings are so restrictive that all classes which can be explanatorily learnt in such Friedberg numberings have only finitely many infinite languages. We also study similar questions for several properties of learners such as consistency, conservativeness, prudence, iterativeness and non U-shaped learning. Besides Friedberg numberings, we also consider the above problems for programming systems with K-recursive grammar equivalence problem.

关键词： learning systems

来源：评论

学校读者我要写书评

暂无评论

Prescribed learning of r.e. classes

引用

thEORETICAL COMPUTER SCIENCE 2009年第19期410卷 1796-1806页

作者： Jain, Sanjay Stephan, Frank Ye, Nan Natl Univ Singapore Dept Comp Sci Singapore 117417 Singapore Natl Univ Singapore Dept Math Singapore 117543 Singapore

this work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypothesis space chosen for the language class in the case of learning uniformly recursive language classes. the concepts of class-comprising (where the learner can choose a uniformly recursively enumerable superclass as the hypothesis space) and class-preserving (where the learner has to choose a uniformly recursively enumerable hypothesis space of the same class) are formulated in their study. In subsequent investigations, uniformly recursively enumerable hypothesis spaces have been considered. In the present work, we extend the above works by considering the question of whether learners can be effectively synthesized from a given hypothesis space in the context of learning uniformly recursively enumerable language classes. in our study, we introduce the concepts of prescribed learning (where there must be a learner for every uniformly recursively enumerable hypothesis space of the same class) and uniform learning (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). It is shown that while for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning;three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypothesis space such that the learner learns every set in the hypothesis space. Moreover the prudent learner can be effectively built from any learner for the class. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Inductive inference Prescribed learning Formal languages Recursion theory

来源：评论

学校读者我要写书评

暂无评论

Separating models of learning with faulty teachers

引用

thEORETICAL COMPUTER SCIENCE 2009年第19期410卷 1903-1912页

作者： Feldman, Vitaly Shah, Shrenik IBM Corp Almaden Res Ctr San Jose CA 95120 USA Harvard Univ Cambridge MA 02138 USA

We study the power of two models of faulty teachers in Valiant's PAC learning model and Angluin's exact learning model. the first model we consider is learning from an incomplete membership oracle introduced by Angluin and Slonim ID. Angluin, D.K. Slonim, Randomly fallible teachers: learning monotone DNF with an incomplete membership oracle, Machine learning 14 (1) (1994) 7-26]. In this model, the answers to a random subset of the learner's membership queries may be missing. the second model we consider is random persistent classification noise in membership queries introduced by Goldman, Kearns and Schapire IS. Goldman, M. Kearns, R. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing 22 (4) (1993) 705-726]. In this model, the answers to a random subset of the learner's membership queries are flipped. We show that in both the PAC and the exact learning models the incomplete membership oracle is strictly stronger than the noisy membership oracle under the assumption that the problem of PAC learning parities with random classification noise is intractable. We also show that under the standard cryptographic assumptions the incomplete membership oracle is strictly weaker than the perfect membership oracle. this generalizes the result of Simon [H. Simon, How many missing answers can be tolerated by query learners? theory of Computing Systems 37 (1) (2004) 77-94] and resolves an open question of Bshouty and Eiron [N. Bshouty, N. Eiron, learning monotone DNF from a teacher that almost does not answer membership queries, journal of Machine learning Research 3 (2002) 49-57]. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Models of learning PAC Exact learning Membership query

来源：评论

学校读者我要写书评

暂无评论

Separating models of learning with faulty teachers

Separating models of learning with faulty teachers

引用

18th international conference on algorithmic learning theory

作者： Feldman, Vitaly Shah, Shrenik Wadhwa, Neal Harvard Univ Cambridge MA 02138 USA

ISBN: (纸本)9783540752240

We study the power of two models of faulty teachers in Angluin's exact learning model. the first model we consider is learning from equivalence and incomplete membership query oracles introduced by Angluin and Slonim [1]. In this model, the answers to a random subset of the learner's membership queries may be missing. the second model we consider is random persistent classification noise in membership queries introduced by Goldman et al. [2]. In this model, the answers to a random subset of the learner's membership queries are flipped. We show that the incomplete membership query oracle is strictly stronger than the membership query oracle with persistent noise under the assumption that the problem of PAC learning parities with noise is intractable. We also show that under the standard cryptographic assumptions the incomplete membership query oracle is strictly weaker than the perfect membership query oracle. this strengthens the result of Simon [3) and resolves an open question of Bshouty and Eiron [4]. Our techniques are based on ideas from coding theory and cryptography.

关键词： learning systems

来源：评论

学校读者我要写书评

暂无评论

Vapnik-chervonenkis dimension of parallel arithmetic computations

Vapnik-chervonenkis dimension of parallel arithmetic computa...

引用

18th international conference on algorithmic learning theory

作者： Alonso, Cesar L. Montana, Jose Luis Univ Oviedo Ctr Inteligencia Artificial Campus Viesques Gijon 33271 Spain Univ Cantabria Dept Matemat Estadistica & Computat Santander 39005 Spain

ISBN: (纸本)9783540752240

We provide upper bounds for the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers whose membership tests are programs described by bounded-depth arithmetic networks. Our upper bounds are of the kind O(k(2)d(2)), where d is the depth of the network (representing the parallel running time) and k is the number of parameters needed to codify the concept. this bound becomes O(k(2)d) when membership tests are described by Boolean-arithmetic circuits. As a consequence we conclude that families of concepts classes having parallel polynomial time algorithms expressing their membership tests have polynomial VC dimension.

关键词： concept learning Vapnik-Chervonenkis dimension Milnor-thom bounds parallel computation formula size

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：