Winnow (algoritmo): differenze tra le versioni

Versione delle 09:25, 21 ago 2025

Versione attuale delle 08:02, 26 ago 2025

(9 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{tmp|algoritmo}}

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]] perutile l'apprendimentoa didefinire un [[classificatore lineare]] a partire da esempi etichettati. ÈSi moltotratta similedi un all'algoritmo delmolto simile al [[percettrone]], macon mentrela differenza che questo utilizzaadotta uno schema di aggiornamento dei pesi additivo, mentre Winnow utilizza uno schema moltiplicativo che gli consente di funzionare molto meglio quandoin presenza di 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 mostratafornita una sequenza di esempi positivi e negativi. Da questiquesta essoil metodo apprende un [[iperpiano]] di decisione che può quindipoi 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 comeda un insieme di [[Caratteristica (apprendimento automatico)|caratteristiche]] a valori [[Booleano (informatica)|booleani]]. L'algoritmo mantienegestisce 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

ovedove <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 buonibuone limitilimitazioni all'errore se <math>\Theta=n/2</math> (vedicfr. discussione in sottobasso).

PerIn fase di addestramento, per ogni esempio presentatofornito, si applica la seguente ''regola di aggiornamento'':

* Se l'esempio è classificato correttamente, non si deve fare nulla.

* Se l'esempio è classificato in modo errato e il risultato corretto è 0, per ogni caratteristica tale che <math>x_{i}=1</math>, il peso corrispondente <math>w_{i}</math> va impostato a 0 (passo di ''retrocessione'').

*: <math>\forall x_{i} = 1, w_{i} =\gets 0</math>

* Se l'esempio è classificato in modo errato e il risultato corretto è 1, per ogni caratteristica <math>x_{i}=1</math>, il peso corrispondente <math>w_{i}</math> va moltiplicato per α<math>\alpha</math> (passo di ''promozione'').

*: <math>\forall x_{i} = 1, w_{i} =\gets \alpha w_{i}</math>

Tipicamente si fissaimposta α<math>\alpha =\gets 2</math>.

Esistono molte varianti di questo approccio di base.

* ''Winnow2'' <ref name=":0" /> è simile, tranne per il fatto che nella fase dinel declassamento i pesi vengono divisi per α<math>\alpha</math> 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]].

== Limiti di d'errore ==

In determinate circostanzecondizioni, siè può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 istanzeesempi in ingresso. Se l'algoritmo Winnow1 utilizza <math>\alpha > 1</math> e <math>\Theta \geq 1/\alpha</math> su una funzione target-obiettivo che è una disgiunzione monotona di <math>k</math> -letterali data da <math>f(x_1,\ldots,x_n)=x_{i_1} \cuplor \cdots \cuplor x_{i_k}</math>, allora per qualsiasi sequenza di istanze il numero totale di errori è limitato da: <mathref>\alpha{{Cita kpubblicazione|autore=Nick (Littlestone|anno=1989|titolo="Mistake \log_\alphabounds \Theta+1)+\frac{nand 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}{\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>

<math>\alpha k ( \log_\alpha \Theta+1)+\frac{n}{\Theta}</math>.

{{Apprendimento automatico}}

== Note ==

<references/>

{{Apprendimento automatico}}

[[Categoria:Algoritmi di classificazione]]