Relationships between learning and information compression based on PAC learning model

✍ Scribed by Eiji Takimoto; Akira Maruoka

• Book ID: 104591597
• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 867 KB
• Volume: 24
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690240805

✦ Synopsis

Abstract

This paper is based on the concept of the learning function, which represents the input‐output relation of the learning algorithm. The learning process and the information compression process are formulated as the PAC learning function and the Occam function, respectively, and their equivalence is discussed. It is shown that the Occam function is always a consistent PAC learning function, while its converse is not always true.

The weak Occam function which is obtained by weakening the condition concerning the information compression power of Occam function is defined anew and it is shown that the weak Occam function is always a consistent PAC learning function. Furthermore, a procedure is shown which derives the weak Occam function from the PAC learning function under a certain condition.