Winnow (algoritmo): differenze tra le versioni

Versione delle 11:12, 21 ago 2025

Versione delle 12:33, 21 ago 2025

(4 versioni intermedie di 2 utenti non mostrate)

Riga 1:

{{Richiesta revisione bozza|ts=20250821112615|richiedente=Capagira|esito=|revisore=}}

{{Bozza|arg=informatica|arg2=|ts=20250821092509|wikidata=Q8025857}}<!-- IMPORTANTE: NON CANCELLARE QUESTA RIGA, SCRIVERE SOTTO -->

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]] utile a definire un [[classificatore lineare]] a partire da esempi etichettati. Si tratta di un algoritmo molto simile al [[percettrone]], con la differenza che questo adotta uno schema di aggiornamento dei pesi additivo, mentre Winnow utilizza uno schema moltiplicativo che gli consente di funzionare molto meglio in presenza di molte dimensioni (''feature'') non rilevanti (da cui il nome, ="[[Crivello|setaccio]]"). L'algoritmo è semplice e si adatta bene a dati ad alta dimensionalità. Durante l'addestramento, a Winnow viene fornita una sequenza di esempi positivi e negativi. Da questa esso apprende un [[iperpiano]] di decisione che può poi 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.

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> è unaun procedurametodo di [[apprendimento automatico]] utile a definire un [[classificatore lineare]] a partire da esempi etichettati. Si tratta di un algoritmo molto simile al [[percettrone]], con la differenza che questo adotta uno schema di aggiornamento dei pesi additivo, mentre Winnow utilizza uno schema moltiplicativo che gli consente di funzionare molto meglio in presenza di molte dimensioni (''feature'') non rilevanti (da cui il nome, ="[[Crivello|setaccio]]"). L'algoritmo è semplice e si adatta bene a dati ad alta dimensionalità. Durante l'addestramento, a Winnow viene fornita una sequenza di esempi positivi e negativi. Da questa essoil metodo apprende un [[iperpiano]] di decisione che può poi essere utilizzato per etichettare nuovi esempi come positivi o negativi. L'algoritmo può essere utilizzato anche in contesti di apprendimento ''online'', dovenei quali la fase di apprendimento e quella di classificazione non sono chiaramentenettamente separate.

== Algoritmo ==

L'algoritmo di base, ''Winnow1'', funziona come segue. Lo spazio delle istanze è <math>X=\{0,1\}^n</math>, ovvero ogni istanza viene descritta da un insieme di [[Caratteristica (apprendimento automatico)|caratteristiche]] a valori [[Booleano (informatica)|booleani]]. L'algoritmo gestisce un vettore di pesi non negativi <math>w_i</math> per <math>i\in \{1,\ldots,n\}</math>, uno per ogni caratteristica, inizialmente impostati a 1. Quando al modello viene fornito un esempio <math>(x_1,\ldots,x_n)</math> da classificare, si applica la tipica ''regola di predizione'' per idei classificatori lineari:

* '''se''' <math>\sum_{i=1}^n w_i x_i > \Theta </math>, '''allora''' si predice 1

* '''altrimenti''' si predice 0

dove <math>\Theta</math> è un numero reale che fa da ''soglia''. Insieme ai pesi, la soglia definisce un iperpiano separatore nello spazio delle istanze. Si ottengono buone limitazioni all'errore se <math>\Theta=n/2</math> (cfr. piùdiscussione in basso).

In fase di addestramento, per ogni esempio fornito, si applica la seguente ''regola di aggiornamento'':

Riga 25 ⟶ 27:

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

== Limiti di d'errore ==

In determinate condizioni, è possibile 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 esempi in ingresso. Se l'algoritmo Winnow1 utilizza <math>\alpha > 1</math> e <math>\Theta \geq 1/\alpha</math> su una funzione-obiettivo che è una disgiunzione monotona di <math>k</math> letterali data da <math>f(x_1,\ldots,x_n)=x_{i_1} \lor \cdots \lor x_{i_k}</math>, allora per qualsiasi sequenza di istanze il numero totale di errori è limitato da: <ref>{{Cita pubblicazione|autore=Nick Littlestone|anno=1989|titolo="Mistake bounds and logarithmic linear-threshold learning algorithms"|rivista=Technical report, University of California, Santa Cruz.|numero=|lingua=en|id=UCSC-CRL-89-11|url=https://www.google.it/books/edition/Mistake_Bounds_and_Logarithmic_Linear_th/X2HbmgEACAAJ}}</ref>

Riga 36 ⟶ 38:

{{Apprendimento automatico}}

{{Categorie bozza|

[[Categoria:Algoritmi di classificazione]]

[[Categoria:Apprendimento automatico]]

}}