VowpalWabbit: Diferencias y escalabilidad

Question

Hola chicos: Estoy tratando de determinar cómo se mantiene el "estado" de VowpalWabbit a medida que crece el tamaño de nuestro conjunto de entrada. En un entorno típico de aprendizaje automático, si tengo 1000 vectores de entrada, esperaría enviarlos todos a la vez, esperar a que se complete una fase de construcción del modelo y luego usar el modelo para crear nuevas predicciones.

En VW, parece que la naturaleza "en línea" del algoritmo cambia este paradigma para que sea más eficiente y capaz de ajustarse en tiempo real.

1) ¿Cómo se implementa esta modificación del modelo en tiempo real?

2) ¿VW toma cada vez más recursos con respecto al tamaño total de los datos de entrada en el tiempo? Es decir, a medida que agrego más datos a mi modelo de VW (cuando es pequeño), ¿los cálculos de ajuste en tiempo real comienzan a tomar más tiempo una vez que el número acumulativo # de entradas de vectores de características aumenta a 1000, 10000 o millones?

Answer 1

Solo para agregar a carlosdc es una buena respuesta.

Algunas de las características que vowpal wabbit aparte, y permitir que se escala a tera-característica (10) de datos-tamaños son:

El vector de peso en línea: vowpal wabbit mantiene una memoria en weight-vector que es esencialmente el vector de pesos para el modelo que está construyendo. Esto es lo que llamas "el estado" en tu pregunta.

tamaño de los datos Unbounded: El tamaño del peso-vector es proporcional a la cantidad de características (variables de entrada independientes), no el número de ejemplos (instancias). Esto es lo que hace vowal wabbit, a diferencia de muchos otros estudiantes (no en línea), escala en el espacio. Como no necesita cargar todos los datos en la memoria como lo hace un típico aprendiz por lotes, aún puede aprender de conjuntos de datos que son demasiado grandes para caber en la memoria.

modo Cluster: vowpal wabbit soportes se ejecutan en múltiples hosts en un clúster, se establece un gráfico de la estructura de árbol binario en los nodos y el uso de la reducción all-reduce de las hojas a la raíz.

Hash truco: vowpal wabbit emplea lo que se llama el hashing trick. Todos los nombres de las funciones se convierten en hash en un número entero usando murmurhash-32. Esto tiene varias ventajas: es muy simple y eficiente en el tiempo al no tener que lidiar con la administración y las colisiones de la tabla hash, a la vez que permite que las características colisionen ocasionalmente.Resulta (en la práctica) que un pequeño número de colisiones características en un conjunto de entrenamiento con miles de características distintas es similar a agregar un término de regularización implícito. Esto contraintuitivamente, a menudo mejora la precisión del modelo en lugar de disminuirlo. También es indiferente a la escasez (o densidad) del espacio de características. Finalmente, permite que los nombres de las entidades de entrada sean cadenas arbitrarias, a diferencia de la mayoría de los estudiantes convencionales que requieren que los nombres/ID de las características sean tanto a) numéricos como b) únicos.

Paralelismo: vowpal wabbit explota CPUs multi-núcleo ejecutando el análisis sintáctico y el aprendizaje en dos hilos separados, además de añadir a su velocidad. Esto es lo que hace que vw sea capaz de aprender tan rápido como lee datos. Resulta que la mayoría de los algoritmos soportados en vw, contrariamente a la intuición, están embotellados por la velocidad IO, en lugar de velocidad de aprendizaje.

puntos de control y el aprendizaje incremental: vowpal wabbit le permite guardar su modelo en el disco mientras se aprende, y luego cargar el modelo y seguir aprendiendo donde lo dejó con la opción --save_resume.

estimación del error de prueba como: La pérdida media calculada por wabbit vowpal "ya que va" es siempre invisible (de la muestra) de datos (*). Esto elimina la necesidad de molestarse con hold-outs pre-planificados o realizar validación cruzada. La tasa de error que ves durante el entrenamiento es 'similar a una prueba'.

allá de los modelos lineales: vowpal wabbit soporta varios algoritmos, incluyendo factorización matriz (más o menos escaso SVD de la matriz), Latent Asignación Dirichlet (LDA), y más. También admite la generación sobre la marcha de interacciones a término (bi-lineal, cuadrática, cúbica y feed-forward sigmoid neural-net con número de unidades especificado por el usuario), clasificación multiclase (además de la regresión básica y binaria) clasificación), y más.

Hay tutoriales y muchos ejemplos en the official vw wiki en github.

(*) Una excepción es si utiliza varias pasadas con la opción --passes N.

Answer 2

VW es una implementación (muy) sofisticada de descenso de gradiente estocástico. Puede leer más sobre el descenso de gradiente estocástico here

Resulta que una buena implementación del descenso de gradiente estocástico es básicamente E/S ligada, va tan rápido como puede obtener los datos, por lo que VW tiene algunas estructuras de datos sofisticadas para "compilar" los datos.

Por lo tanto, la respuesta a la pregunta (1) es hacer descenso de gradiente estocástico y la respuesta a la pregunta (2) definitivamente no lo es.