NeuroCOLT workshop
on
Generalisation Bounds Less than 0.5
Windsor, 29 April - 2 May 2002
Cumberland Lodge

Compression Bounds and the Set Covering Machine

John Shawe-Taylor (joint work with Mario Marchand)

The basis of the set covering machine is introduced with reference to Valiant and Haussler's work. The approach is motivated by analogy to the data-dependent approach of Support Vector Machines. The presentation covers the theoretical analysis that motivates the optimisation of the sparsity. Furthermore bounds on the size of solution when compared with the best achievable are given. Finally, experimental results are presented for a number of UCI datasets showing that the theoretical generalisation bounds are not only non-trivial, but can also be used to guide model selection with accuracy comparable to cross-validation.