LEARNING UNREALIZABLE TASKS FROM MINIMUM ENTROPY QUERIES

In supervised learning, learning from queries rather than from random examples can improve generalization performance significantly. We stud y the performance of query learning for unrealizable tasks, where the student cannot learn from the perfectly. As a simple model scenario of this kind, we consider a linear perceptron student learning a general nonlinear perceptron teacher. Two kinds of queries for maximum inform ation gain, i.e. minimum entropy, are investigated: minimum student sp ace entropy (MSSE) queries, which are appropriate if the teacher space is unknown, and minimum teacher space entropy (MTSE) queries, which c an be used if the teacher space is assumed to be known, but a student of a simpler form has deliberately been chosen. We find that for MSSE queries, the structure of the student space determines the efficacy of query learning. MTSE queries, on the other hand, which we investigate for the extreme case of a binary perceptron teacher, lead to a higher generalization error than random examples, due to a lack of feedback about the progress of the student in the way queries are selected.