Towards a Linear-Data Monotone Wrapper Algorithm For Machine Learning Algorithms

Abstract

Machine learning algorithms (learners) are typically expected to produce monotone learning curves, meaning that their performance improves as the size of the training dataset increases. However, it is important to note that this behavior is not universally observed. Recently monotonicity of learning curves has gained renewed attention, as several authors have proposed ’wrapper’ algorithms; algorithms that attempt at filtering the hypotheses produced by a learner to turn them into a monotone learner, even if the learner itself is not monotone. Such wrappers use part of the training data as validation data, and each newly produced hypothesis is evaluated using this validation data. However, with each new hypothesis, the validation data grows in size exponentially. As such the wrapper is data-hungry, using up to 85% of the training data as validation data in some cases. This paper investigates what happens when a linearly growing validation sample is used instead. Is it enough to retain monotonicity? We proof that selecting the best performing hypothesis from a finite set of hypotheses, based on a validation sample that grows linearly, results in a monotone learning curve. However, when introducing a new hypothesis with each increase in the validation sample size, it has been observed that this selection process does not demonstrate monotonic behavior. The authors of this paper hope that this work provides key insight into how to choose from a set of hypotheses in a monotone way, and that the work may be a stepping stone for a fully functioning linear-data monotone wrapper algorithm.