Grant: Discovery Grants Program - Individual
Université Laval
$27,000.00
Learning algorithms and risk bounds for sample-compressed Bayes classifiers
FY 2008-09
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
122405-2006
Name nom
Marchand, Mario
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2006
Award amount
27000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Partie
3
Nb partie
5
Application title
Learning algorithms and risk bounds for sample-compressed Bayes classifiers
Keyword
NA
Application summary
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.