Conservativeness and monotonicity for learning algorithms
Eiji Takimoto, Akira Maruoka · 1993
In the framework of PAC-learning model, relationships between learning processes and information compressing processes are investigated.Information compressing processes are formulated as weak Occam algorithms.A weak Occarn algorithm is a deterministic polynomial time aJgorit hm that, when given m examples of unknown function, outputs, with high probability, a representation of a function that is consistent with the examples and belongs to a function class with complexity o(m).It has been shown that a weak Occam algorithm is also a consistent PAC-learning algorithm.In this extended abstract, it is shown that the converse does not hold by giving a PAClearning algorithm that is not a weak Occarn algorithm.and also some natural properties, caUed cowervativene.w and monotonicity, for learning algorithms that might help the converse hold are given.In particular, the conditions that make a conservative PAC-learning algorithm a weak Occam algorithm are given, and it is shown that, under some natural conditions, a monotone PAC-learning algorithm for a hypothesis class can be transformed to a weak Occam algorithm without changing the hypothesis class.