En el aprendizaje automático , el hash de características , también conocido como el truco de hash (por analogía con el truco del kernel ), es una forma rápida y eficiente de vectorizar características , es decir, convertir características arbitrarias en índices en un vector o matriz. [1] [2] Funciona aplicando una función hash a las características y usando sus valores hash como índices directamente, en lugar de buscar los índices en una matriz asociativa . Este truco a menudo se atribuye a Weinberger et al., Pero existe una descripción mucho anterior de este método publicada por John Moody en 1989. [2] [1]
Ejemplo motivador
En una tarea típica de clasificación de documentos , la entrada al algoritmo de aprendizaje automático (tanto durante el aprendizaje como durante la clasificación) es texto libre. A partir de esto, se construye una representación de una bolsa de palabras (BOW): los tokens individuales se extraen y se cuentan, y cada token distinto en el conjunto de entrenamiento define una característica (variable independiente) de cada uno de los documentos en los conjuntos de entrenamiento y prueba.
Sin embargo, los algoritmos de aprendizaje automático se definen normalmente en términos de vectores numéricos. Por lo tanto, las bolsas de palabras para un conjunto de documentos se consideran como una matriz de documentos de términos donde cada fila es un solo documento y cada columna es una sola característica / palabra; la entrada i , j en dicha matriz captura la frecuencia (o peso) del j 'ésimo término del vocabulario en el documento i . (Una convención alternativa intercambia las filas y columnas de la matriz, pero esta diferencia es irrelevante). Por lo general, estos vectores son extremadamente escasos, de acuerdo con la ley de Zipf .
El enfoque común es construir, en el momento del aprendizaje o antes de eso, una representación de diccionario del vocabulario del conjunto de entrenamiento y usarlo para asignar palabras a índices. Las tablas hash y los intentos son candidatos comunes para la implementación de diccionarios. Por ejemplo, los tres documentos
- A John le gusta ver películas.
- A Mary también le gustan las películas.
- A John también le gusta el fútbol.
se puede convertir, usando el diccionario
Término | Índice |
---|---|
John | 1 |
gustos | 2 |
a | 3 |
mirar | 4 |
películas | 5 |
María | 6 |
también | 7 |
además | 8 |
fútbol | 9 |
a la matriz plazo-documento
(Se eliminó la puntuación, como es habitual en la clasificación y agrupación de documentos).
El problema con este proceso es que dichos diccionarios ocupan una gran cantidad de espacio de almacenamiento y aumentan de tamaño a medida que aumenta el conjunto de formación. [3] Por el contrario, si el vocabulario se mantiene fijo y no se incrementa con un conjunto de entrenamiento creciente, un adversario puede intentar inventar nuevas palabras o errores ortográficos que no están en el vocabulario almacenado para eludir un filtro de aprendizaje automático. Esta dificultad es la razón por la que se ha probado la función hash para el filtrado de spam en Yahoo! Investigación . [4]
Tenga en cuenta que el truco de hash no se limita a la clasificación de texto y tareas similares a nivel de documento, sino que se puede aplicar a cualquier problema que implique un gran número de funciones (quizás ilimitadas).
Vectorización de características usando el truco hash
En lugar de mantener un diccionario, un vectorizador de características que usa el truco de hash puede construir un vector de una longitud predefinida aplicando una función hash h a las características (por ejemplo, palabras), luego usando los valores hash directamente como índices de características y actualizándolos el vector resultante en esos índices. Aquí, asumimos que característica en realidad significa vector de características.
función hash_vectorizer ( características : matriz de cadena , N : entero ) : x : = nuevo vector [ N ] para f en características : h : = hash ( f ) x [ h mod N ] + = 1 return x
Por lo tanto, si nuestro vector de características es ["gato", "perro", "gato"] y la función hash es Si es "gato" y Si es perro". Consideremos que la dimensión del vector de la característica de salida ( N ) es 4. Luego, la salida x será [0,2,1,0]. Se ha sugerido que se utilice una segunda función hash de salida de un solo bit ξ para determinar el signo del valor de actualización, para contrarrestar el efecto de las colisiones hash . [2] Si se utiliza dicha función hash, el algoritmo se convierte en
función hash_vectorizer ( características : matriz de cadena , N : entero ) : x : = nuevo vector [ N ] para f en características : h : = hash ( f ) idx : = h mod N if ξ ( f ) == 1 : x [ idx ] + = 1 más : x [ idx ] - = 1 retorno x
El pseudocódigo anterior realmente convierte cada muestra en un vector. En cambio, una versión optimizada solo generaría un flujo de ( h , ξ ) pares y dejaría que los algoritmos de aprendizaje y predicción consumieran dichos flujos; se puede implementar un modelo lineal como una única tabla hash que representa el vector de coeficientes.
Propiedades
ξ ( f ₁) | ξ ( f ₂) | Valor final, ξ ( f ₁) + ξ ( f ₂) |
---|---|---|
-1 | -1 | -2 |
-1 | 1 | 0 |
1 | -1 | 0 |
1 | 1 | 2 |
Cuando se usa una segunda función hash ξ para determinar el signo del valor de una característica, la media esperada de cada columna en la matriz de salida se vuelve cero porque ξ hace que algunas colisiones se cancelen. [2] Por ejemplo, suponga que una entrada contiene dos características simbólicas f ₁ y f ₂ que chocan entre sí, pero no con ninguna otra característica en la misma entrada; entonces hay cuatro posibilidades que, si no hacemos suposiciones sobre ξ , tienen la misma probabilidad, como se indica en la tabla de la derecha.
En este ejemplo, hay un 50% de probabilidad de que se cancele la colisión de hash. Se pueden utilizar múltiples funciones hash para reducir aún más el riesgo de colisiones. [5]
Además, si φ es la transformación implementada por un truco hash con un signo hash ξ (es decir, φ ( x ) es el vector de características producido para una muestra x ), entonces los productos internos en el espacio hash son insesgados:
donde la expectativa se toma sobre la función hash φ . [2] Se puede verificar quees un núcleo semidefinido positivo . [2] [6]
Extensiones y variaciones
El trabajo reciente extiende el truco del hash a las asignaciones supervisadas de palabras a índices, [7] que se aprenden explícitamente para evitar colisiones de términos importantes.
Aplicaciones y rendimiento práctico
Ganchev y Dredze demostraron que en aplicaciones de clasificación de texto con funciones hash aleatorias y varias decenas de miles de columnas en los vectores de salida, el hash de características no tiene por qué tener un efecto adverso en el rendimiento de la clasificación, incluso sin la función hash firmada. [3] Weinberger y col. aplicó su variante de hash al problema del filtrado de spam , formulando esto como un problema de aprendizaje de múltiples tareas donde las características de entrada son pares (usuario, característica) de modo que un solo vector de parámetro captura los filtros de spam por usuario, así como un filtro global para varios cientos de miles de usuarios, y descubrió que la precisión del filtro aumentó. [2]
Implementaciones
Las implementaciones del truco hash están presentes en:
- Apache Mahout [5]
- Gensim [8]
- scikit-learn [9]
- sofia-ml [10]
- Vowpal Wabbit
- Apache Spark [11]
- R [12]
- TensorFlow [13]
Ver también
- Filtro de floración
- Esbozo de conteo mínimo
- Ley de montones
- Hash sensible a la localidad
- MinHash
Referencias
- ↑ a b Moody, John (1989). "Aprendizaje rápido en jerarquías de múltiples resoluciones" (PDF) . Avances en sistemas de procesamiento de información neuronal .
- ^ a b c d e f g Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Hash de funciones para el aprendizaje multitarea a gran escala (PDF) . Proc. ICML.
- ^ a b K. Ganchev; M. Dredze (2008). Pequeños modelos estadísticos mediante mezcla aleatoria de características (PDF) . Proc. Taller ACL08 HLT sobre procesamiento de lenguajes móviles.
- ^ Josh Attenberg; Kilian Weinberger; Alex Smola; Anirban Dasgupta; Martin Zinkevich (2009). "Filtrado colaborativo de spam con el truco hash" . Boletín de virus .
- ^ a b Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Ellen (2012). Mahout en acción . Manning. págs. 261-265.
- ^ Shi, Q .; Petterson J .; Dror G .; Langford J .; Smola A .; Strehl A .; Vishwanathan V. (2009). Hash Kernels . AISTATS.
- ^ Bai, B .; Weston J .; Grangier D .; Collobert R .; Sadamasa K .; Qi Y .; Chapelle O .; Weinberger K. (2009). Indexación semántica supervisada (PDF) . CIKM. págs. 187–196.
- ^ "gensim: corpora.hashdictionary - Construir asignaciones de palabras <-> id" . Radimrehurek.com . Consultado el 13 de febrero de 2014 .
- ^ "4.1. Extracción de características - documentación de scikit-learn 0.14" . Scikit-learn.org . Consultado el 13 de febrero de 2014 .
- ^ "sofia-ml - Suite de Algoritmos Incrementales Rápidos para Machine Learning. Incluye métodos para el aprendizaje de modelos de clasificación y ranking, utilizando Pegasos SVM, SGD-SVM, ROMMA, Perceptrón Pasivo-Agresivo, Perceptrón con Márgenes y Regresión Logística" . Consultado el 13 de febrero de 2014 .
- ^ "Hashing TF" . Consultado el 4 de septiembre de 2015 .
Asigna una secuencia de términos a sus frecuencias de términos utilizando el truco de hash.
- ^ "FeatureHashing: crea una matriz de modelo a través de la función hash con una interfaz de fórmula" .
- ^ "tf.keras.preprocessing.text.hashing_trick - TensorFlow Core v2.0.1" . Consultado el 29 de abril de 2020 .
Convierte un texto en una secuencia de índices en un espacio hash de tamaño fijo.
enlaces externos
- Representaciones hash para aprendizaje automático en el sitio web de John Langford
- ¿Qué es el "truco de hash"? - MetaOptimize Q + A