Winnow (algoritmo): differenze tra le versioni

Versione delle 20:43, 20 ago 2025

Versione delle 20:47, 20 ago 2025

Riga 1:

L' algoritmo '''Winnow''' <ref name=":0">{{Cita pubblicazione|nome=Nick|cognome=Littlestone|data=1988-04-01|titolo=Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm|rivista=Machine Learning|volume=2|numero=4|pp=285–318|lingua=en|accesso=2025-08-20|doi=10.1023/A:1022869011914|url=https://doi.org/10.1023/A:1022869011914}}</ref> è una procedura di [[apprendimento automatico]] per l'apprendimento di un [[classificatore lineare]] da esempi etichettati. È molto simile all'algoritmo del [[percettrone]], ma mentre questo utilizza uno schema v di aggiornamento dei pesi, mentre Winnow utilizza uno schema moltiplicativo che gli consente di funzionare molto meglio quando molte dimensioni (''feature'') non sono rilevanti (da cui il nome, che significa [[Crivello|setaccio]]). L'algoritmo è semplice e si adatta bene a dati ad alta dimensionalità. Durante l'addestramento, a Winnow viene mostrata una sequenza di esempi positivi e negativi. Da questi esso apprende un [[iperpiano]] di decisione che può quindi essere utilizzato per etichettare nuovi esempi come positivi o negativi. L'algoritmo può essere utilizzato anche in contesti di apprendimento online, dove la fase di apprendimento e quella di classificazione non sono chiaramente separate.

== Algoritmo ==

Riga 21:

Esistono molte varianti di questo approccio di base.

* ''Winnow2'' <ref name=":0" /> è simile, tranne per il fatto che nella fase di declassamento i pesi vengono divisi per α invece di essere impostati a 0.

* ''Balanced Winnow'' lavora con due insiemi di pesi e quindi due iperpiani. Questo può quindi essere generalizzato per [[classificazione multi-etichetta]].

Riga 27:

In determinate circostanze, si può dimostrare che il numero di errori commessi da Winnow durante l'apprendimento ha un [[Maggiorante e minorante|limite superiore]] che non dipende dal numero di istanze in ingresso. Se l'algoritmo Winnow1 utilizza <math>\alpha > 1</math> e <math>\Theta \geq 1/\alpha</math> su una funzione target che è una disgiunzione monotona di <math>k</math> -letterali data da <math>f(x_1,\ldots,x_n)=x_{i_1}\cup \cdots \cup x_{i_k}</math>, allora per qualsiasi sequenza di istanze il numero totale di errori è limitato da: <math>\alpha k ( \log_\alpha \Theta+1)+\frac{n}{\Theta}</math> <ref>

Nick Littlestone (1989). "Mistake bounds and logarithmic linear-threshold learning algorithms". Technical report UCSC-CRL-89-11, University of California, Santa Cruz.</ref>

{{Apprendimento automatico}}

== Note ==

<references/>

<nowiki>

[[Categoria:Algoritmi di classificazione]]

[[Categoria:Apprendimento automatico]]</nowiki>