Learning algorithms and risk bounds for sample-compressed Bayes classifiers

该研究项目属于被称为机器学习的人工智能子领域。更具体地说，我们研究的是众所周知的分类问题（也称为模式识别问题）。许多应用的成功，例如生物信息学，计算机视觉和自然语言处理中出现的应用，通常受到用于解决潜在分类问题的学习算法的效率的强烈限制。在过去的40年里，已经提出了许多学习算法，但往往没有一个是足够有效的，以满足应用程序的要求。因此，我们的主要长期目标是更好地理解有效学习的可能性，并找到在这些情况下可以学习的最有效的算法。为了朝着这个方向前进，我们计划继续探索学习算法，例如集合覆盖机，它可以产生样本压缩分类器。这些分类器仅由训练数据的一个小子集识别，并且我们有良好的性能保证，这是根据风险界限指定的。风险界限是分类器在新的（看不见的）示例上产生分类错误的概率的界限。此外，风险界限可从分类器在训练数据上实现的内容计算。在我们寻求获得更好的分类器的过程中，我们现在想要设计有效的学习算法来产生样本压缩分类器的加权多数投票。对于这项任务，我们首先建议搜索这种类型的分类器的一个紧密的风险界，然后提出有效的算法来找到一个分类器实现低风险界。我们还希望将这种方法扩展到部分训练数据未标记的常见情况，以及错误分类示例所造成的损失取决于示例的类的情况。严格的风险边界应该提供新的优化问题，并希望，新的和更有效的学习算法。

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.