A Potential-based Framework for Multi-class Learning with Partial Feedback
Professor Rong Jin
Department of Computer and Science Engineering
Michigan State University
Abstract :
We study the problem of online multi-class learning with partial feedback: in each trial of online learning, instead of providing the true class label for a given instance, the oracle will only reveal to the learner if the predicted class label is correct. We present a general framework for online multi-class learning with partial feedback that adapts the potential-based gradient descent approaches ~\cite{bianchi-2006-prediction}. The generality of the proposed framework is verified by the fact that Banditron is indeed a special case of our work. We propose an exponential gradient algorithm for online multi-class learning with partial feedback. Compared to the Banditron algorithm, the exponential gradient algorithm is advantageous in that its mistake bound is independent from the dimension of data, making it suitable for classifying high dimensional data. We also investigate the problem of how to determine the optimal tradeoff between exploration and exploitation in multi-class learning with partial feedback. Our empirical study with text categorization, optimal letter recognition, and ad selection shows promising results of the proposed methods.
Bio:
Dr. Rong Jin is an Associate Professor in the Department of Computer and Science Engineering at Michigan State University. His research is focused on statistical machine learning and its application to information retrieval, and has published over 120 conference and journal articles on related topics. Dr. Jin holds a B.A. in Engineering from Tianjin University, an M.S. in Physics from Beijing University, and an M.S. and Ph.D. in Computer Science from Carnegie Mellon University. He joined the Dept. of Computer and Science Engineering at MSU since 2003, and received the NSF Career Award in 2006.