Lifelong Learning in Costly Feature Spaces
Lifelong Learning in Costly Feature Spaces
复制标题
DOI：
10.1016/j.tcs.2019.11.010
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Avrim Blum;Vaishnavh Nagarajan
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;Vaishnavh Nagarajan
机器学习系统的一个重要的长期目标是构建学习代理，像人类一样，可以在其一生中学习许多任务，并使用这些任务中的信息来提高其有效完成任务的能力。在这项工作中，我们的目标是提供新的理论见解，这种模式的潜力。特别是，我们提出了一个终身学习的框架，坚持一个新的概念，资源效率是至关重要的，在许多现实世界的领域，功能评估是昂贵的。也就是说，我们的学习者的目标是重用之前学习的相关任务中的信息，以功能高效的方式学习未来的任务。此外，我们认为新的组合方式，学习任务可以涉及。具体来说，我们设计终身学习算法的两个结构不同的和广泛使用的家庭的目标函数：决策树/列表和单项式/多项式。我们还为这些算法提供了强有力的特征效率保证;事实上，我们表明，为了学习未来的目标，我们只需要稍微多一点的特征评估每个训练示例比需要预测的任意示例使用这些目标。我们还提供了一个不可知模型中的保证算法，其中不是所有的目标都相互关联。最后，我们还提供了这些模型中终身学习者的性能下限，这些模型在某些条件下实际上是紧的。
An important long-term goal in machine learning systems is to build learning agents that, like humans, can learn many tasks over their lifetime, and moreover use information from these tasks to improve their ability to do so efficiently. In this work, our goal is to provide new theoretical insights into the potential of this paradigm. In particular, we propose a lifelong learning framework that adheres to a novel notion of resource efficiency that is critical in many real-world domains where feature evaluations are costly. That is, our learner aims to reuse information from previously learned related tasks to learn future tasks in afeature-efficientmanner. Furthermore, we consider novel combinatorial ways in which learning tasks can relate. Specifically, we design lifelong learning algorithms for two structurally different and widely used families of target functions: decision trees/lists and monomials/polynomials. We also provide strong feature-efficiency guarantees for these algorithms; in fact, we show that in order to learn future targets, we need only slightly more feature evaluations per training example than what is needed to predict on an arbitrary example using those targets. We also provide algorithms with guarantees in an agnostic model where not all the targets are related to each other. Finally, we also provide lower bounds on the performance of a lifelong learner in these models, which are in fact tight under some conditions.