Winnow (algoritmo)

L' algoritmo Winnow ^[1] è 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 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 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

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

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

ove ${\displaystyle \Theta }$  è un numero reale che fa da soglia. Insieme ai pesi, la soglia definisce un iperpiano separatore nello spazio delle istanze. Si ottengono buoni limiti se ${\displaystyle \Theta =n/2}$  (vedi sotto).

Per ogni esempio presentato, si applica la seguente regola di aggiornamento:

• Se l'esempio è classificato correttamente, non 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}=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 α (passo di promozione).

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

Tipicamente si fissa α = 2.

Esistono molte varianti di questo approccio di base.

• Winnow2 ^[1] è 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.

Limiti di errore

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

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. ^ Nick Littlestone (1989). "Mistake bounds and logarithmic linear-threshold learning algorithms". Technical report UCSC-CRL-89-11, University of California, Santa Cruz.