|
使用本地成员资格查询学习
Learning Using Local Membership Queries |
|
| |
| 课程网址: |
http://videolectures.net/colt2013_awasthi_queries/
|
| 主讲教师: |
Pranjal Awasthi
|
| 开课单位: |
卡内基梅隆大学
|
| 开课时间: |
2013-08-09
|
| 课程语种: |
英语
|
| 中文简介: |
我们引入了一种新的成员资格查询 MQ(membership queries)学习模型，其中学习算法仅限于接近从底层分布中抽取的随机示例的查询点。学习模型介于PAC模型（Valiant，1984）和PAC MQ模型（允许查询为任意点）之间。会员查询算法在机器学习从业者中不受欢迎。除了自适应查询贴标签器的明显困难之外，还观察到查询不自然的点会导致人类贴标签者的噪音增加（Lang和Baum，1992）。这激发了我们对学习算法的研究，这些算法使得查询与从数据分布生成的示例很接近。我们将注意力限制在n维布尔超立方体上定义的函数，并且如果其汉明距离来自某个示例，则表示成员资格查询是本地的。 （随机）训练数据最多为O（log（n））。我们在此模型中显示以下结果：1。在{0,1} n上的稀疏多项式（具有R中的系数）的类是在使用O（log（n））局部查询的大类局部平滑分布下可学习的多项式时间。该类还包括O（log（n））深度决策树类。多项式大小决策树类是使用O（log（n））局部查询在产品分布下可学习的多项式时间。多项式大小DNF公式的类可以在均匀分布下使用时间nO（log（log（n））中的O（log（n））局部查询来学习。此外，我们证明了许多将所提出的模型与传统PAC模型和PAC MQ模型相关的结果。
|
| 课程简介: |
We introduce a new model of membership query (MQ) learning, where the learning algorithm is restricted to query points that are close to random examples drawn from the underlying distribution. The learning model is intermediate between the PAC model (Valiant,1984) and the PAC+MQ model (where the queries are allowed to be arbitrary points). Membership query algorithms are not popular among machine learning practitioners. Apart from the obvious difficulty of adaptively querying labellers, it has also been observed that querying unnatural points leads to increased noise from human labellers (Lang and Baum, 1992). This motivates our study of learning algorithms that make queries that are close to examples generated from the data distribution. We restrict our attention to functions defined on the n-dimensional Boolean hypercube and say that a membership query is local if its Hamming distance from some example in the (random) training data is at most O(log(n)). We show the following results in this model: 1. The class of sparse polynomials (with coefficients in R) over {0,1}n is polynomial time learnable under a large class of locally smooth distributions using O(log(n))-local queries. This class also includes the class of O(log(n))-depth decision trees. 2. The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries. 3. The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time nO(log(log(n))). 4. In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model.
|
| 关 键 词: |
查询算法; 数据分布; 学习模型
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2021-06-27：zyk
|
| 阅读次数: |
42
|
|
图 书 馆