RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.13, n.3 (39), 2005/

A Deterministic and Polynomial Modified Perceptron Algorithm

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(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:

Fulltext

Adobe PDF document0.23 Mb