Margin-Sparsity Trade-off for the Set Covering Machine
Mohak Shah (School of Information Technology and Engineering, University of Ottawa)
NICTA SML SEMINARDATE: 2005-11-16
TIME: 10:00:00 - 11:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
One of the recent advances in the direction of Sample Compression based algorithms has come in the form of the Set Covering Machine (SCM) Algorithm that aims at learning Conjunction or Disjunction of Boolean features built on data. In addition to providing good classification accuracy it has also been possible to provide good theoretical guarantees on the generalization error of the resulting classifier.
In this talk, I will present a new learning algorithm for the SCM and a tight data-compression risk bound that the learner can use for choosing the appropriate tradeoff between the sparsity of a classifier and the magnitude of its separating margin. The empirical results show how such a margin-sparsity trade-off can lead to better classification accuracy. This is a joint work with Francois Laviolette and Mario Marchand from Universiti Laval. The presentation will be self contained and will include a brief introduction to the classical SCM for clarity and ease.
Finally, I would outline some major directions of extending the Set Covering Machine framework that we are examining currently or plan to undertake in future.
BIO:
Mohak Shah is a Ph.D. candidate at the University of Ottawa, Canada under the supervision of Mario Marchand. His Research interests span Machine Learning, both core and applied esp. to Bioinformatics and Business, and Learning Theory. His current research is focused on studying Sample Compression based algorithms, more specifically extensions to the Set Covering Machine framework. He is also currently working on studying the language of Electronic Negotiations in business settings. Mohak was named the Arnold Smith Commonwealth Scholar by the Royal Commonwealth Society of Canada for 2001-02 and is a recipient of the Ontario Graduate Scholarship (International) for 2004-2006. He was also awarded the National Scholarship by the Govt. of India in 1995.
