Aventar (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 usa un esquema multiplicativo que le permite funcionar mucho mejor cuando muchas dimensiones son irrelevantes (de ahí su nombre winnow ). Es un algoritmo simple que se adapta bien a datos de alta dimensión. Durante el entrenamiento, a Winnow se le muestra una secuencia de ejemplos positivos y negativos. De estos aprende un hiperplano de decisión que luego puede usarse para etiquetar ejemplos novedosos 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 de clasificación no están claramente separadas.

Algoritmo

El algoritmo básico, Winnow1, es el siguiente. El espacio de instancia es , es decir, cada instancia se describe como un conjunto de características con valores booleanos . El algoritmo mantiene ponderaciones no negativas para , que inicialmente se establecen en 1, una ponderación para cada característica. Cuando al alumno se le da 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 predice 1 ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }$
• De lo contrario predice 0

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

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

• Si un ejemplo está clasificado correctamente, no hagas nada.
• Si un ejemplo se predice incorrectamente 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 predijo 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 de α es 2.

Hay 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. Luego, esto se puede generalizar para la clasificación de etiquetas múltiples .

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 casos que se le presentan. Si el algoritmo Winnow1 utiliza y en una función objetivo 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", Aprendizaje automático 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.