Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 11, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Michel Verlinden
The Sublinear Perceptron is a recent algorithm for linear binary classification with support vector machines. It was recently developed by K.L. Clarkson, E. Hazan and D.P. Woodruff. This algorithm approximately solves the problem of finding a hyperplane isolating a set of vectors into a single half-space. The hyperplane is optimal in the sense that the distance of the vectors nearest to the hyperplane is maximized. The algorithm runs in sublinear time which implies that it does not require to read the whole input. It involves randomization based on a novel sampling techniques and a new multiplicative update method.
This talk will present the Sublinear Perceptron and the performance results obtained with our implementation. We shall also present the extension of the algorithm to non-linear classification. The preservation of sublinear-time complexity with non-linear classifiers induces further randomization of the Sublinear Perceptron.
Automatic MiSe System Software Version 1.4803M | admin login