id: 02089359
dt: a
an: 02089359
au: Mesterharm, Chris
ti: Tracking linear-threshold concepts with Winnow.
so: Kivinen, Jyrki (ed.) et al., Computational learning theory. 15th annual
    conference, COLT 2002, Sydney, Australia, July 8‒10, 2002.
    Proceedings. Berlin: Springer (ISBN 3-540-43836-X). Lect. Notes Comput.
    Sci. 2375, 138-152 (2002).
py: 2002
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: http://link.springer.de/link/service/series/0558/bibs/2375/23750138.htm
ab: Summary: In this paper, we give a mistake-bound for learning arbitrary
    linear-threshold concepts that are allowed to change over time in the
    on-line model of learning. We use a standard variation of the Winnow
    algorithm and show that the bounds for learning shifting
    linear-threshold functions have many of the same advantages that the
    traditional Winnow algorithm has on fixed concepts. These benefits
    include a weak dependence on the number of irrelevant attributes,
    inexpensive runtime, and robust behavior against noise. In fact, we
    show that the bound for the tracking version of Winnow has even better
    performance with respect to irrelevant attributes. Let $X\in[0,1]^n$ be
    an instance of the learning problem. In the traditional algorithm, the
    bound depends on $\ln n$. In this paper, the shifting concept bound
    depends approximately on $\max {\ln\left({\left\Vert X
    \right\Vert_1}\right)}$.
rv: