Authors: Olof Barr
Abstract
We construct a modified perceptron algorithm that is deterministic, polynomial and also as fast as previous known algorithms. The algorithm runs in time O(mn
3lognlog(1/ρ)) , where m is the number of examples, n the number of dimensions and ρ is approximately the size of the margin. We also construct a non-deterministic modified perceptron algorithm running in timeO(mn
2lognlog(1/ρ)) .
Olof Barr
Centre for Mathematical Sciences,
Lund University
Sweden
E-mail:
Fulltext
–
0.23 Mb