The Role of the Environment in On-Line Learning

近年来，机器学习的理论研究受到了广泛的关注。这个研究项目的一个主要目标是了解在线模型中学习者与其环境交互的变化如何影响学习的复杂性。以前的工作已经表明，学习的复杂性取决于如何选择实例(或多个实例)。通常的假设是对手选择实例，但这次调查将集中在可选的在线模型上。首先，情景将是学习者选择实例的研究。这项工作的一部分将是开发一种新的模型，在这种模型中，每个查询都有很小的成本，但每个错误都有很大的成本。这样的模型将有利于学习算法，这些算法犯的错误很少，同时仍然需要适度数量的例子。第二种选择是让教师执行实例选择。它计划将一种教学模式正规化，要求教师找到最佳的授课方式，以便任何“专心”的学生都能学到这门课。这个模型，将被用来研究教学的复杂性。也将考虑对学习者施加进一步限制(而不将学习者限制在某些特定算法)的该模型的变体。

Recently, considerable attention has been devoted to the theoretical study of machine learning. A primary goal of this research project is to understand how changes in the learner's interaction with its environment in an on-line model influence the complexity of learning. Previous work has shown that the complexity of learning depends on how the instances (or examples) are selected. The usual assumption is that the adversary selects the instances, but this investigation will center on alternative on-line models. First, the situation will be studies in which the learner selects the instances. Part of this work will be the development of a new model in which each query has a small cost, yet each mistake has a large cost. Such a model would favor learning algorithms that make few mistakes while still requesting a modest number of examples. A second alternative is to have a teacher perform the instance selection. It is planned to formalize a model of teaching that requires the teacher to find the best way to present the lesson so that any student who "pays attention" learns the lesson. This model, will be used to study the complexity of teaching. Variations of this model that place further restrictions on the learner (without confining the learner to some particular algorithm) will also be considered.