El algoritmo de aventar [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 de perceptrón usa un esquema de actualización de peso aditivo, 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, se muestra a Winnow una secuencia de ejemplos positivos y negativos. De estos aprende un hiperplano de decisiónque luego se puede usar para etiquetar ejemplos nuevos como positivos o negativos. El algoritmo también se puede utilizar en el entorno de aprendizaje en línea , donde el aprendizaje y la fase de clasificación no están claramente separados.
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 valor booleano . El algoritmo mantiene pesos no negativos. por , que inicialmente se establecen en 1, un peso para cada función. Cuando se le da un ejemplo al alumno, aplica la regla de predicción típica para clasificadores lineales:
- Si , luego predice 1
- De lo contrario, predice 0
Aquí es un número real que se llama umbral . Junto con los pesos, el umbral define un hiperplano divisor en el espacio de la instancia. Se obtienen buenos límites si (vea abajo).
Para cada ejemplo con el que se presenta, el alumno aplica la siguiente regla de actualización:
- Si un ejemplo está clasificado correctamente, no haga 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).
- Si un ejemplo se predice incorrectamente y el resultado correcto fue 1, para cada característica , el peso correspondiente multiplicado por α (paso de promoción).
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. Balanced Winnow mantiene dos conjuntos de pesos y, por lo tanto, dos hiperplanos. Luego, esto puede generalizarse 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 comete Winnow a medida que aprende tiene un límite superior que es independiente del número de instancias con las que se presenta. Si el algoritmo Winnow1 usa y en una función de destino que es un -Disyunción monótona literal dada por , entonces, para cualquier secuencia de instancias, el número total de errores está limitado por: . [2]
Referencias
- ↑ a b Nick Littlestone (1988). "Aprendizaje rápido cuando abundan los atributos irrelevantes: un nuevo algoritmo de umbral lineal", Machine Learning 285–318 (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.