Boosting and online learning for classification and ranking

This dissertation utilizes boosting and online learning techniques to address several real-world problems in ranking and classification. Boosting is an optimization tool that works in the function space (as opposed to parameter space) and aims to find a model in batch mode. Typically, boosting iteratively constructs weak hypotheses with respect to different distributions over a fixed set of training instances and adds them to a final hypothesis. Online learning is the problem of learning a model when the instances are provided over trials. In each trial, a new sample is presented to the learner, the learner predicts its class label and then receives some feedback (partial or complete). The learner updates its model by utilizing the feedback and then a new trial starts.;We consider several learning problems, including the usage of side information in ranking and classification, learning to rank by optimizing a well-known information retrieval measure called NDCG, and online classification with partial feedback.;Using side information to improve the performance of learning techniques has been one research focus of machine learning community for the last decade. In this dissertation, we utilize the abundance of unlabeled instances to improve the performance of multi-class classification, and exploit the existence of a base ranker to improve the performance of learning to rank, both using the boosting technique.;Direct optimization of information retrieval evaluation measures such as NDCG and MAP has received increasing attention in the recent years. It is a difficult task because these measures evaluate the retrieval performance based on the ranking list of documents induced by the ranking function, and therefore they are non-continuous and non-differentiable. To overcome this difficulty, we propose to optimize the expected value of NDCG and utilize boosting technique as the optimization tool.;Online classification with partial feedback is recently introduced and has applications in contextual advertisement and recommender systems. We propose a general framework for this problem based on exploration vs. exploitation tradeoff technique and introduce effective approaches to automatically tune the exploration vs. exploitation tradeoff parameter.