Hash de características

En aprendizaje automático , el hash de características , también conocido como truco de hash (por analogía con el truco del kernel ), es una forma rápida y eficiente en 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 un arreglo asociativo . Además de su uso para codificar valores no numéricos, el hash de características también se puede usar 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 este, se construye una representación de 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.

Los algoritmos de aprendizaje automático, sin embargo, se definen típicamente en términos de vectores numéricos. Por lo tanto, las bolsas de palabras para un conjunto de documentos se consideran una matriz término-documento donde cada fila es un documento individual y cada columna es una característica/palabra individual; 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 dispersos , según la ley de Zipf .

El enfoque común consiste en construir, durante el aprendizaje o antes, una representación en diccionario del vocabulario del conjunto de entrenamiento y utilizarla para asignar palabras a índices. Las tablas hash y los tries 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

a la matriz término-documento

{\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 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 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 nuevas palabras o errores ortográficos que no estén en el vocabulario almacenado para eludir un filtro de aprendizaje automático. Para abordar este desafío, Yahoo! Research intentó utilizar el hash de características para sus filtros de spam. ^{[ 4 ]}

Cabe señalar que la técnica de hash no se limita a la clasificación de texto y tareas similares a nivel de documento, sino que puede aplicarse a cualquier problema que involucre un gran número de características (quizás ilimitado).

Motivación matemática

Matemáticamente, un token es un elemento $t$ en un conjunto finito (o infinitamente numerable) $T$ . Supongamos que solo necesitamos procesar un corpus finito, entonces podemos colocar todos los tokens que aparecen en el corpus en $T$ , lo que significa que $T$ es finito. Sin embargo, supongamos que queremos procesar todas las palabras posibles formadas por las letras inglesas, entonces $T$ es infinitamente numerable.

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

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

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

De hecho, podemos flexibilizar ligeramente el requisito: basta con tener una inyección de cálculo rápido. $h:T\to \{1,...,n\}$ , luego usar $\phi (t)=e_{h(t)}$ .

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

En este punto, acabamos de especificar que $h$ Debe ser una función hash. Así llegamos a la idea del hash de características.

Algoritmos

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

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

En primer lugar, se especifican dos funciones hash: el hash del kernel $h:T\to \{1,2,...,n\}$ y el signo hash $\zeta :T\to \{-1,+1\}$ A continuación, se define la función hash de características: $\phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}$ Finalmente, extienda esta función hash de características a cadenas de tokens mediante $\phi :T^{*}\to \mathbb {R} ^{n},\quad \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\phi (t_{j})$ dónde $T^{*}$ es el conjunto de todas las cadenas finitas que constan de tokens en $T$ .

De forma equivalente, $\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 acerca de la propiedad geométrica de $\phi$ , pero $T$ , por sí mismo, es solo un conjunto de tokens, no podemos imponerle una estructura geométrica excepto la topología discreta, que es generada por la métrica discreta . Para hacerlo más agradable, lo elevamos a $T\to \mathbb {R} ^{T}$ y levantar $\phi$ de $\phi :T\to \mathbb {R} ^{n}$ a ${\displaystyle \phi$ por extensión lineal : $\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}$ Hay una suma infinita allí, que debe manejarse de inmediato. En esencia, solo hay dos maneras de manejar los infinitos. Se puede imponer una métrica, luego tomar su completación , para permitir sumas infinitas bien comportadas, o se puede exigir que nada sea realmente infinito, solo potencialmente infinito . Aquí, optamos por el camino del infinito potencial, restringiendo $\mathbb {R} ^{T}$ contener únicamente vectores con soporte finito : $\forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}$ , solo un número finito de entradas de $(x_{t})_{t\in T}$ son distintos de cero.

Defina un producto interno en $\mathbb {R} ^{T}$ de la forma obvia: $\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$ Como nota al margen, si $T$ es infinito, entonces el espacio de producto interno $\mathbb {R} ^{T}$ no está completo . Tomar su completitud nos llevaría a un espacio de Hilbert , que permite sumas infinitas bien comportadas.

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

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

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

Prueba

Por linealidad de la expectativa, $\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$ Ahora, $\mathbb {E} [\zeta (t)\zeta (t')]={\begin{cases}1\quad {\text{ if }}t=t'\\0\quad {\text{ if }}t\neq t'\\\end{cases}}$ , ya que asumimos $\zeta$ es imparcial. Por lo tanto, continuamos $\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 demostración anteriores interpretan la función hash binaria. $\zeta$ no como una función determinista de tipo $T\to \{-1,+1\}$ pero como un vector binario aleatorio $\{-1,+1\}^{T}$ con entradas imparciales, lo que significa que $Pr(\zeta (t)=+1)=Pr(\zeta (t)=-1)={\frac {1}{2}}$ para cualquier $t\in T$ .

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

Implementación en pseudocódigo

En lugar de mantener un diccionario, un vectorizador de características que utiliza la técnica de hash puede construir un vector de longitud predefinida aplicando una función hash $h$ a las características (por ejemplo, palabras), utilizando los valores hash directamente como índices de características y actualizando el vector resultante en esos índices. Aquí, asumimos que "característica" se refiere en realidad a un 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 return x

Por lo tanto, si nuestro vector de características es ["gato","perro","gato"] y la función hash es $h(x_{f})=1$ si $x_{f}$ es "gato" y $2$ si $x_{f}$ es "perro". Tomemos la dimensión del vector de características de salida ( N ) como 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 de hash . ^[²^] Si se utiliza dicha función hash, el algoritmo se convierte en

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 sino : x [ idx ] -= 1 retornar x

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

Extensiones y variaciones

Hashing de características aprendidas

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

Si $t'$ es raro, entonces la degradación del rendimiento es pequeña, ya que el modelo siempre podría ignorar el caso raro y pretender que todo $v$ medio $t$ Sin embargo, si ambos son comunes, la degradación puede ser grave.

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

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 hashing de características no tiene por qué 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 capturaba filtros de spam por usuario, así como un filtro global para varios cientos de miles de usuarios, y encontraron 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 $M\in \mathbb {R} ^{n\times n}$ como un diccionario, con claves en $n\times n$ y valores en $\mathbb {R}$ Luego, como es habitual en los diccionarios hash, se puede utilizar una función hash. $h:\mathbb {N} \times \mathbb {N} \to m$ y, por lo tanto, representan una matriz como un vector en $\mathbb {R} ^{m}$ , sin importar cuán grande $n$ es. Con matrices virtuales, construyeron HashedNets , que son grandes redes neuronales que ocupan solo pequeñas cantidades de almacenamiento. ^{[ 6 ]}

Implementaciones

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

Véase también

Filtro de Bloom : estructura de datos para la pertenencia aproximada a un conjunto.
Esquema de conteo-min : estructura de datos probabilística en informática
Ley de Heaps : heurística para palabras distintas en un documento. Páginas que muestran descripciones breves de los destinos de redireccionamiento.
Hashing sensible a la localidad : técnica algorítmica que utiliza funciones hash
MinHash – Técnica de minería de datos

Referencias

1 2 Moody, John (1989). "Aprendizaje rápido en jerarquías de multirresolución" (PDF) . Advances in Neural Information Processing Systems . Archivado del original (PDF) el 11 de abril de 2016. Recuperado el 14 de diciembre de 2018 .
1 2 3 4 5 6 7 Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Hashing de características para aprendizaje multitarea a gran escala (PDF) . Actas de ICML.
1 2 K. Ganchev; M. Dredze (2008). Pequeños modelos estadísticos mediante mezcla aleatoria de características (PDF) . Actas del Taller ACL08 HLT sobre Procesamiento del Lenguaje Móvil.
↑ Josh Attenberg; Kilian Weinberger; Alex Smola; Anirban Dasgupta; Martin Zinkevich (2009). "Filtrado colaborativo de spam con el truco del hash" . Virus Bulletin .
^ Bai, B.; Weston J.; Granger D.; Collobert R.; Sadamasa K.; Qi Y.; Capilla O.; Weinberger K. (2009). Indexación semántica supervisada (PDF) . CIKM. págs. 187-196 .
↑ Chen, Wenlin; Wilson, James; Tyree, Stephen; Weinberger, Kilian; Chen, Yixin (2015-06-01). "Compresión de redes neuronales con el truco del hashing" . Conferencia internacional sobre aprendizaje automático . PMLR: 2285–2294 . arXiv : 1504.04788 .
^ Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Elena (2012). Mahout en acción . Manning. págs. 261-265 .
↑ "gensim: corpora.hashdictionary – Construir asignaciones de palabra<->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 - Conjunto de algoritmos incrementales rápidos para el aprendizaje automático. Incluye métodos para aprender modelos de clasificación y ordenación, 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érmino utilizando el truco del hashing.
↑ "FeatureHashing: Crea una matriz de modelo mediante hash de características con una interfaz de fórmula" . 10 de enero de 2024.
↑ "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.
↑ "dask_ml.feature_extraction.text.HashingVectorizer — documentación de dask-ml 2021.11.17" . ml.dask.org . Consultado el 22/11/2021 .

Enlaces externos

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

[Moody-1] 1 2 Moody, John (1989). "Aprendizaje rápido en jerarquías de multirresolución" (PDF) . Advances in Neural Information Processing Systems . Archivado del original (PDF) el 11 de abril de 2016. Recuperado el 14 de diciembre de 2018 .

[Weinberger-2] 1 2 3 4 5 6 7 Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Hashing de características para aprendizaje multitarea a gran escala (PDF) . Actas de ICML.

[mobilenlp-3] 1 2 K. Ganchev; M. Dredze (2008). Pequeños modelos estadísticos mediante mezcla aleatoria de características (PDF) . Actas del Taller ACL08 HLT sobre Procesamiento del 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.; Granger D.; Collobert R.; Sadamasa K.; Qi Y.; Capilla 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 (2015-06-01). "Compresión de redes neuronales con el truco del hashing" . Conferencia internacional sobre aprendizaje automático . PMLR: 2285–2294 . arXiv : 1504.04788 .

[mahout-7] Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Elena (2012). Mahout en acción . Manning. págs. 261-265 .

[8] "gensim: corpora.hashdictionary – Construir asignaciones de palabra<->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 - Conjunto de algoritmos incrementales rápidos para el aprendizaje automático. Incluye métodos para aprender modelos de clasificación y ordenación, 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 modelo 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/11/2021 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]