We consider the problem of online learning in a changing environment under sparse user feedback. Specifically, we address the classification of music types according to a user’s preferences for a hearing aid application. The classifier, operating under limited computational resources, must be capable of adjusting to types of data not represented in the training set, and to changing user demands. The user provides feedback only occasionally, prompting the classifier to change its state. We propose an online learning algorithm capable of incorporating information from unlabeled data by a semi-supervised strategy, and demonstrate that the use of unlabeled examples significantly improves classification performance if the ratio of labeled points is small.