Winnow (algoritmo)

El algoritmo winnow ^[1] es una técnica de aprendizaje automático para aprender un clasificador lineal a partir de ejemplos etiquetados. Es muy similar al algoritmo del perceptrón . Sin embargo, el algoritmo del perceptrón utiliza un esquema aditivo de actualización de peso, mientras que Winnow utiliza un esquema multiplicativo que le permite funcionar mucho mejor cuando muchas dimensiones son irrelevantes (de ahí su nombre winnow ). Es un algoritmo simple que escala bien a datos de alta dimensión. Durante el entrenamiento, a Winnow se le muestra una secuencia de ejemplos positivos y negativos. A partir de estos, aprende un hiperplano de decisión que luego puede usarse para etiquetar ejemplos nuevos como positivos o negativos. El algoritmo también se puede utilizar en el entorno de aprendizaje en línea , donde la fase de aprendizaje y la de clasificación no están claramente separadas.

Algoritmo

El algoritmo básico, Winnow1, es el siguiente. El espacio de instancias es , es decir, cada instancia se describe como un conjunto de características con valores booleanos . El algoritmo mantiene pesos no negativos para , que inicialmente se establecen en 1, un peso para cada característica. Cuando se le da al alumno un ejemplo , aplica la regla de predicción típica para clasificadores lineales: ${\displaystyle X=\{0,1\}^{n}}$ ${\displaystyle w_{i}}$ ${\displaystyle i\in \{1,\ldots ,n\}}$ ${\displaystyle (x_{1},\ldots ,x_{n})}$

• Si , entonces predecir 1 ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }$
• De lo contrario, predecir 0

Aquí hay un número real que se llama umbral . Junto con los pesos, el umbral define un hiperplano divisor en el espacio de instancia. Se obtienen buenos límites si (ver a continuación). ${\displaystyle \Theta }$ ${\displaystyle \Theta =n/2}$

Para cada ejemplo que se le presenta, el alumno aplica la siguiente regla de actualización:

• Si un ejemplo está correctamente clasificado, no haga nada.
• Si se predice incorrectamente un ejemplo y el resultado correcto fue 0, para cada característica , el peso correspondiente se establece en 0 (paso de degradación). ${\displaystyle x_{i}=1}$ ${\displaystyle w_{i}}$

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

• Si un ejemplo se predice incorrectamente y el resultado correcto fue 1, para cada característica , el peso correspondiente se multiplica por α (paso de promoción). ${\displaystyle x_{i}=1}$ ${\displaystyle w_{i}}$

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

Un valor típico para α es 2.

Existen muchas variaciones de este enfoque básico. Winnow2 ^[1] es similar, excepto que en el paso de degradación los pesos se dividen por α en lugar de establecerse en 0. Winnow equilibrado mantiene dos conjuntos de pesos y, por lo tanto, dos hiperplanos. Esto se puede generalizar para la clasificación de múltiples etiquetas .

Límites de error

En determinadas circunstancias, se puede demostrar que el número de errores que Winnow comete a medida que aprende tiene un límite superior que es independiente del número de instancias que se le presentan. Si el algoritmo Winnow1 utiliza y en una función de destino que es una disyunción monótona -literal dada por , entonces para cualquier secuencia de instancias el número total de errores está limitado por: . ^[2] ${\displaystyle \alpha >1}$ ${\displaystyle \Theta \geq 1/\alpha }$ ${\displaystyle k}$ ${\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\cup \cdots \cup x_{i_{k}}}$ ${\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}$

Referencias

1. Nick Littlestone (1988). "Aprender rápidamente cuando abundan los atributos irrelevantes: un nuevo algoritmo de umbral lineal", Machine Learning 285–318(2).
2. Nick Littlestone (1989). "Límites de error y algoritmos de aprendizaje de umbral lineal logarítmico". Informe técnico UCSC-CRL-89-11, Universidad de California, Santa Cruz.