Authors: Olof Barr
– 0.23 Mb
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(mn3lognlog(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(mn2lognlog(1/ρ)) .Olof Barr
Centre for Mathematical Sciences,
Lund University
Sweden
E-mail:
Centre for Mathematical Sciences,
Lund University
Sweden
E-mail:
Fulltext
– 0.23 Mb
