Bozza:Winnow (algoritmo)

L'algoritmo Winnow ^[1] è un metodo 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, ="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 il 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, nei quali la fase di apprendimento e quella di classificazione non sono nettamente separate.

Algoritmo

L'algoritmo di base, Winnow1, funziona come segue. Lo spazio delle istanze è ${\displaystyle X=\{0,1\}^{n}}$ , ovvero ogni istanza viene descritta da un insieme di caratteristiche a valori booleani. L'algoritmo gestisce un vettore di pesi non negativi ${\displaystyle w_{i}}$  per ${\displaystyle i\in \{1,\ldots ,n\}}$ , uno per ogni caratteristica, inizialmente impostati a 1. Quando viene fornito un esempio ${\displaystyle (x_{1},\ldots ,x_{n})}$  da classificare, si applica la tipica regola di predizione dei classificatori lineari:

• se ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }$ , allora si predice 1
• altrimenti si predice 0

dove ${\displaystyle \Theta }$  è 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 ${\displaystyle \Theta =n/2}$  (cfr. discussione in basso).

In fase di addestramento, per ogni esempio fornito, 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 ${\displaystyle x_{i}=1}$ , il peso corrispondente ${\displaystyle w_{i}}$  va impostato a 0 (passo di retrocessione).

  ${\displaystyle \forall x_{i}=1,w_{i}\gets 0}$ 

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

  ${\displaystyle \forall x_{i}=1,w_{i}\gets \alpha w_{i}}$ 

Tipicamente si imposta ${\displaystyle \alpha \gets 2}$ .

Esistono molte varianti di questo approccio di base.

• Winnow2 ^[1] è simile, tranne per il fatto che nel declassamento i pesi vengono divisi per ${\displaystyle \alpha }$  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 d'errore

In determinate condizioni, è possibile dimostrare che il numero di errori commessi da Winnow durante l'apprendimento ha un limite superiore che non dipende dal numero di esempi in ingresso. Se l'algoritmo Winnow1 utilizza ${\displaystyle \alpha >1}$  e ${\displaystyle \Theta \geq 1/\alpha }$  su una funzione-obiettivo che è una disgiunzione monotona di ${\displaystyle k}$  letterali data da ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\lor \cdots \lor x_{i_{k}}}$ , allora per qualsiasi sequenza di istanze il numero totale di errori è limitato da: ^[2]

${\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}$ .

Note

1. (EN) Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, in Machine Learning, vol. 2, n. 4, 1º aprile 1988, pp. 285–318, DOI:10.1023/A:1022869011914. URL consultato il 20 agosto 2025.
2. ^ (EN) Nick Littlestone, "Mistake bounds and logarithmic linear-threshold learning algorithms", in Technical report, University of California, Santa Cruz., 1989, UCSC-CRL-89-11.

Questa pagina sarà elencata nelle seguenti categorie una volta spostata nel namespace principale.

Categorie:

• Algoritmi di classificazione
• Apprendimento automatico