Hashing de características

Vectorización de características mediante una función hash

En el aprendizaje automático , el hash de características , también conocido como truco de hash (por analogía con el truco del núcleo ), es una forma rápida y que ahorra espacio 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 (después de una operación de módulo), en lugar de buscar los índices en una matriz asociativa . Además de su uso para codificar valores no numéricos, el hash de características también se puede utilizar para la reducción de dimensionalidad . ^[2]

Este truco se atribuye a menudo a Weinberger et al. (2009), ^[2] pero existe una descripción mucho anterior de este método publicada por John Moody en 1989. ^[1]

Motivación

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 en bolsa de palabras (BOW): se extraen y cuentan los tokens individuales, y cada token distinto en el conjunto de entrenamiento define una característica (variable independiente) de cada uno de los documentos tanto en el conjunto de entrenamiento como en el de prueba.

Sin embargo, los algoritmos de aprendizaje automático suelen definirse en términos de vectores numéricos. Por lo tanto, las bolsas de palabras de un conjunto de documentos se consideran una matriz término-documento 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 término j 'ésimo 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 dispersos , de acuerdo con la ley de Zipf .

El enfoque común es construir, en el momento del aprendizaje o antes de él, una representación de diccionario del vocabulario del conjunto de entrenamiento y utilizarla 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 María también le gustan las películas.
• A Juan también le gusta el fútbol.

se puede convertir, usando el diccionario

a la matriz término-documento

${\displaystyle {\begin{pmatrix}{\textrm {John}}&{\textrm {likes}}&{\textrm {to}}&{\textrm {watch}}&{\textrm {movies}}&{\textrm {Mary}}&{\textrm {too}}&{\textrm {also}}&{\textrm {football}}\\1&1&1&1&1&0&0&0&0\\0&1&0&0&1&1&1&0&0\\1&1&0&0&0&0&0&1&1\end{pmatrix}}}$

(Se eliminó la puntuación, como es habitual en la clasificación y agrupamiento de documentos).

El problema de este proceso es que estos diccionarios ocupan una gran cantidad de espacio de almacenamiento y aumentan de tamaño a medida que crece el conjunto de entrenamiento. ^[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 palabras nuevas o errores ortográficos que no estén en el vocabulario almacenado para eludir un filtro aprendido por máquina. Para abordar este desafío, Yahoo! Research intentó utilizar el hash de características para sus filtros de spam. ^[4]

Tenga en cuenta que el truco del 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 involucre grandes (quizás ilimitadas) cantidades de características.

Motivación matemática

Matemáticamente, un token es un elemento de un conjunto finito (o infinito contable) . Supongamos que solo necesitamos procesar un corpus finito, entonces podemos poner todos los tokens que aparecen en el corpus en , lo que significa que es finito. Sin embargo, supongamos que queremos procesar todas las palabras posibles formadas por las letras del inglés, entonces es infinito contable. ${\displaystyle t}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$

La mayoría de las redes neuronales sólo pueden operar con entradas vectoriales reales, por lo que debemos construir una función "diccionario" . ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$

Cuando es finito, de tamaño , entonces podemos usar la codificación one-hot para mapearlo en . Primero, enumeramos arbitrariamente , luego definimos . En otras palabras, asignamos un índice único a cada token, luego mapeamos el token con índice al vector de base unitaria . ${\displaystyle T}$ ${\displaystyle |T|=m\leq n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle T=\{t_{1},t_{2},..,t_{m}\}}$ ${\displaystyle \phi (t_{i})=e_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle e_{i}}$

La codificación one-hot es fácil de interpretar, pero requiere que se mantenga la enumeración arbitraria de . Dado un token , para calcular , debemos encontrar el índice del token . Por lo tanto, para implementar de manera eficiente, necesitamos una biyección que sea rápida de calcular , entonces tenemos . ${\displaystyle T}$ ${\displaystyle t\in T}$ ${\displaystyle \phi (t)}$ ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle \phi }$ ${\displaystyle h:T\to \{1,...,m\}}$ ${\displaystyle \phi (t)=e_{h(t)}}$

De hecho, podemos relajar un poco el requisito: basta con tener una inyección rápida de calcular y luego usar . ${\displaystyle h:T\to \{1,...,n\}}$ ${\displaystyle \phi (t)=e_{h(t)}}$

En la práctica, no existe una manera sencilla de construir una inyección eficiente . Sin embargo, no necesitamos una inyección estricta, sino solo una inyección aproximada . Es decir, cuando , probablemente deberíamos tener , de modo que probablemente . ${\displaystyle h:T\to \{1,...,n\}}$ ${\displaystyle t\neq t'}$ ${\displaystyle h(t)\neq h(t')}$ ${\displaystyle \phi (t)\neq \phi (t')}$

En este punto, acabamos de especificar que debe ser una función hash. De esta manera llegamos a la idea del hash de características. ${\displaystyle h}$

Algoritmos

Hashing de características (Weinberger et al. 2009)

El algoritmo de hash de características básicas presentado en (Weinberger et al. 2009) ^[2] se define de la siguiente manera.

Primero, se especifican dos funciones hash: la hash de núcleo y la hash de signo . A continuación, se define la función hash de característica: Por último, se extiende esta función hash de característica a cadenas de tokens mediante donde es el conjunto de todas las cadenas finitas que constan de tokens en . ${\displaystyle h:T\to \{1,2,...,n\}}$ ${\displaystyle \zeta :T\to \{-1,+1\}}$ $${\displaystyle \phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}}$$ $${\displaystyle \phi :T^{*}\to \mathbb {R} ^{n},\quad \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\phi (t_{j})}$$ ${\displaystyle T^{*}}$ ${\displaystyle T}$

De manera equivalente, $${\displaystyle \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\zeta (t_{j})e_{h(t_{j})}=\sum _{i=1}^{n}\left(\sum _{j:h(t_{j})=i}\zeta (t_{j})\right)e_{i}}$$

Propiedades geométricas

Queremos decir algo sobre la propiedad geométrica de , pero , por sí mismo, es solo un conjunto de tokens, no podemos imponerle una estructura geométrica excepto la topología discreta, que se genera por la métrica discreta . Para hacerlo más agradable, lo elevamos a , y lo elevamos de a por extensión lineal: Hay una suma infinita allí, que debe manejarse de inmediato. Esencialmente, solo hay dos formas de manejar infinitos. Uno puede imponer una métrica, luego tomar su completitud , para permitir sumas infinitas de buen comportamiento, o uno puede exigir que nada sea realmente infinito, solo potencialmente infinito . Aquí, vamos por el camino potencial-infinito, restringiendo para contener solo vectores con soporte finito : , solo un número finito de entradas de son distintas de cero. ${\displaystyle \phi }$ ${\displaystyle T}$ ${\displaystyle T\to \mathbb {R} ^{T}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$ ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$ $${\displaystyle \phi ((x_{t})_{t\in T})=\sum _{t\in T}x_{t}\zeta (t)e_{h(t)}=\sum _{i=1}^{n}\left(\sum _{t:h(t)=i}x_{t}\zeta (t)\right)e_{i}}$$ ${\displaystyle \mathbb {R} ^{T}}$ ${\displaystyle \forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}}$ ${\displaystyle (x_{t})_{t\in T}}$

Definamos un producto interno de la manera obvia: como nota al margen, si es infinito, entonces el espacio del producto interno no está completo . Si tomamos su completitud, obtendremos un espacio de Hilbert , que permite sumas infinitas con buen comportamiento. ${\displaystyle \mathbb {R} ^{T}}$ $${\displaystyle \langle e_{t},e_{t'}\rangle ={\begin{cases}1,{\text{ if }}t=t',\\0,{\text{ else.}}\end{cases}}\quad \langle x,x'\rangle =\sum _{t,t'\in T}x_{t}x_{t'}\langle e_{t},e_{t'}\rangle }$$ ${\displaystyle T}$ ${\displaystyle \mathbb {R} ^{T}}$

Ahora tenemos un espacio de producto interno, con suficiente estructura para describir la geometría de la función hash de características . ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$

Primero, podemos ver por qué se llama " hash de kernel ": nos permite definir un kernel por En el lenguaje del "truco del kernel", es el kernel generado por el "mapa de características" Nótese que este no es el mapa de características que estábamos usando, que es . De hecho, hemos estado usando otro kernel , definido por El beneficio de aumentar el hash del kernel con el hash binario es el siguiente teorema, que establece que es una isometría "en promedio". ${\displaystyle h}$ ${\displaystyle K:T\times T\to \mathbb {R} }$ $${\displaystyle K(t,t')=\langle e_{h(t)},e_{h(t')}\rangle }$$ ${\displaystyle K}$ $${\displaystyle \varphi :T\to \mathbb {R} ^{n},\quad \varphi (t)=e_{h(t)}}$$ ${\displaystyle \phi (t)=\zeta (t)e_{h(t)}}$ ${\displaystyle K_{\zeta }:T\times T\to \mathbb {R} }$ $${\displaystyle K_{\zeta }(t,t')=\langle \zeta (t)e_{h(t)},\zeta (t')e_{h(t')}\rangle }$$ ${\displaystyle h}$ ${\displaystyle \zeta }$ ${\displaystyle \phi }$

Teorema (enunciado intuitivamente)  :  si el hash binario es imparcial (lo que significa que toma valor con igual probabilidad), entonces es una isometría en expectativa: ${\displaystyle \zeta }$ ${\displaystyle -1,+1}$ ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$ $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\langle x,x'\rangle .}$$

Prueba

Por linealidad de la expectativa, ahora, , ya que asumimos que es insesgado. Por lo tanto, continuamos $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t,t'\in T}(x_{t}x'_{t'})\cdot \mathbb {E} [\zeta (t)\zeta (t')]\cdot \langle e_{h(t)},e_{h(t')}\rangle }$$ ${\displaystyle \mathbb {E} [\zeta (t)\zeta (t')]={\begin{cases}1\quad {\text{ if }}t=t'\\0\quad {\text{ if }}t\neq t'\\\end{cases}}}$ ${\displaystyle \zeta }$ $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t\in T}(x_{t}x'_{t})\langle e_{h(t)},e_{h(t)}\rangle =\langle x,x'\rangle }$$

La afirmación y prueba anteriores interpretan la función hash binaria no como una función determinista de tipo , sino como un vector binario aleatorio con entradas imparciales, lo que significa que para cualquier . ${\displaystyle \zeta }$ ${\displaystyle T\to \{-1,+1\}}$ ${\displaystyle \{-1,+1\}^{T}}$ ${\displaystyle Pr(\zeta (t)=+1)=Pr(\zeta (t)=-1)={\frac {1}{2}}}$ ${\displaystyle t\in T}$

Esta es una buena imagen intuitiva, aunque no rigurosa. Para una afirmación y una demostración rigurosas, véase ^[2]

Implementación de pseudocódigo

En lugar de mantener un diccionario, un vectorizador de características que utiliza el truco del hash puede construir un vector de una longitud predefinida aplicando una función hash h a las características (por ejemplo, palabras), y luego utilizando los valores hash directamente como índices de características y actualizando el vector resultante en esos índices. Aquí, asumimos que característica en realidad significa vector de características.

 función hashing_vectorizer ( características : matriz de cadenas , N : entero ) : x := nuevo vector [ N ] para f en características : h := hash ( f ) x [ h mod N ] += 1 devuelve 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". Supongamos que la dimensión del vector de características de salida ( N ) es 4. Entonces 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 ${\displaystyle h(x_{f})=1}$ ${\displaystyle x_{f}}$ ${\displaystyle 2}$ ${\displaystyle x_{f}}$

 función hashing_vectorizer ( características : matriz de cadenas , N : entero ) : x := nuevo vector [ N ] para f en características : h := hash ( f ) idx := h mod N si ξ ( f ) == 1 : x [ idx ] += 1 de lo contrario : x [ idx ] -= 1 devuelve x                                     

El pseudocódigo anterior convierte cada muestra en un vector. Una versión optimizada solo generaría un flujo de pares y dejaría que los algoritmos de aprendizaje y predicción consumieran dichos flujos; entonces se puede implementar un modelo lineal como una única tabla hash que represente el vector de coeficientes. ${\displaystyle (h,\zeta )}$

Extensiones y variaciones

Hashing de características aprendidas

El hash de características generalmente sufre colisión de hashes, lo que significa que existen pares de tokens diferentes con el mismo hash: . Un modelo de aprendizaje automático entrenado con palabras con hashes de características tendría dificultades para distinguir y , esencialmente porque es polisémico . ${\displaystyle t\neq t',\phi (t)=\phi (t')=v}$ ${\displaystyle t}$ ${\displaystyle t'}$ ${\displaystyle v}$

Si es poco frecuente, la degradación del rendimiento es pequeña, ya que el modelo siempre podría ignorar el caso poco frecuente y hacer como si todos los medios fueran así . Sin embargo, si ambos son comunes, la degradación puede ser grave. ${\displaystyle t'}$ ${\displaystyle v}$ ${\displaystyle t}$

Para manejar esto, se pueden entrenar funciones hash supervisadas que eviten mapear tokens comunes a los mismos vectores de características. ^[5]

Aplicaciones y desempeño 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 necesita tener un efecto adverso en el rendimiento de la clasificación, incluso sin la función hash con signo. ^[3]

Weinberger et al. (2009) aplicaron su versión de hash de características al aprendizaje multitarea y, en particular, al filtrado de spam , donde las características de entrada son pares (usuario, característica) de modo que un único vector de parámetros capturó filtros de spam por usuario, así como un filtro global para varios cientos de miles de usuarios, y descubrieron que la precisión del filtro aumentó. ^[2]

Chen et al. (2015) combinaron la idea del hash de características y la matriz dispersa para construir "matrices virtuales": matrices grandes con pequeños requisitos de almacenamiento. La idea es tratar una matriz como un diccionario, con claves en y valores en . Luego, como es habitual en los diccionarios hash, se puede usar una función hash y, por lo tanto, representar una matriz como un vector en , sin importar cuán grande sea. Con matrices virtuales, construyeron HashedNets , que son grandes redes neuronales que solo requieren pequeñas cantidades de almacenamiento. ^[6] ${\displaystyle M\in \mathbb {R} ^{n\times n}}$ ${\displaystyle n\times n}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle h:\mathbb {N} \times \mathbb {N} \to m}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle n}$

Implementaciones

Las implementaciones del truco de hash están presentes en:

• Mahout apache ^[7]
• Simulación genética ^[8]
• aprendizaje científico ^[9]
• sofia-ml ^[10]
• Conejo de votos
• Apache Spark ^[11]
• R ^[12]
• Flujo tensorial ^[13]
• Dask-ML ^[14]

Véase también

• Filtro Bloom  : estructura de datos para la pertenencia aproximada a un conjunto
• Esquema de conteo mínimo  : estructura de datos probabilística en informática
• Ley de Heaps  : heurística para palabras distintas en un documento
• Hashing sensible a la localidad  : técnica algorítmica que utiliza hash
• MinHash  – Técnica de minería de datos

Referencias

1. Moody, John (1989). "Aprendizaje rápido en jerarquías de múltiples resoluciones" (PDF) . Avances en sistemas de procesamiento de información neuronal .
2. Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Hashing de características para aprendizaje multitarea a gran escala (PDF) . Proc. ICML.
3. K. Ganchev; M. Dredze (2008). Modelos estadísticos pequeños mediante mezcla aleatoria de características (PDF) . Proc. Taller ACL08 HLT sobre procesamiento de lenguaje móvil.
4. Josh Attenberg; Kilian Weinberger; Alex Smola; Anirban Dasgupta; Martin Zinkevich (2009). "Filtrado colaborativo de spam con el truco del hash". Virus Bulletin .
5. 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.
6. Chen, Wenlin; Wilson, James; Tyree, Stephen; Weinberger, Kilian; Chen, Yixin (1 de junio de 2015). "Compresión de redes neuronales con el truco de hash". Conferencia internacional sobre aprendizaje automático . PMLR: 2285–2294. arXiv : 1504.04788 .
7. Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Ellen (2012). Mahout en acción . Manning. págs. 261–265.
8. "gensim: corpora.hashdictionary – Construir asignaciones de palabras<->id". Radimrehurek.com . Consultado el 13 de febrero de 2014 .
9. "4.1. Extracción de características — documentación de scikit-learn 0.14". Scikit-learn.org . Consultado el 13 de febrero de 2014 .
10. "sofia-ml - Suite de algoritmos incrementales rápidos para aprendizaje automático. Incluye métodos para aprender 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 .
11. "Hashing TF" . Consultado el 4 de septiembre de 2015 . Asigna una secuencia de términos a sus frecuencias de término utilizando el truco del hashing.
12. "FeatureHashing: crea una matriz de modelos mediante hash de características con una interfaz de fórmula". 10 de enero de 2024.
13. "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 de hash de tamaño fijo.
14. "dask_ml.feature_extraction.text.HashingVectorizer — documentación de dask-ml 2021.11.17". ml.dask.org . Consultado el 22 de noviembre de 2021 .

Enlaces externos

• Representaciones hash para el aprendizaje automático en el sitio web de John Langford
• ¿Qué es el "truco del hash"? - Preguntas y respuestas de MetaOptimize