Learning algorithms and risk bounds for sample-compressed Bayes classifiers

点击翻译按钮获取中文摘要

This research project belongs to the subfield of artificial intelligence known as machine learning. More specifically, we work on the well known classification problem (also called the pattern recognition problem). The success of many applications, such as those arising in bioinformatics, computer vision and natural language processing, is often strongly limited by the efficiency of the learning algorithm used to solve an underlying classification problem. Many learning algorithms have been proposed over the past forty years but, too often, none of them are efficient enough to meet the requirements of the application. Consequently, our main long-term objective is to understand better the circumstances under which efficient learning is possible and find the most efficient algorithms that can learn in these circumstances. To progress in this direction we plan to continue our exploration of learning algorithms, such as the set covering machine, that produce sample-compressed classifiers. These are classifiers that are identified only by a small subset of the training data and for which we have a good performance guaranteed which is specified in terms of a risk bound. A risk bound is a bound on the probability that a classifier makes a classification error on a new (unseen) example. Furthermore, a risk bound is computable from what a classifier achieves on the training data. In our quest to obtain better classifiers, we now want to design efficient learning algorithms for producing a weighted majority-vote of sample-compressed classifiers. For this task, we first propose to search for a tight risk bound for this type of classifiers and then propose efficient algorithms to find a classifier achieving a low risk bound. We also want to extend this approach the the common cases where part of the training data is unlabelled and to the cases where the loss incurred on misclassifying an example depends on the example's class. Tight risk bounds should provide new optimization problems and, hopefully, new and more efficient learning algorithms.