Método Hash

En el aprendizaje automático (AA), el método hash, (por analogía con el método del kernel ), también conocido como atributos hash, es una forma rápida y eficiente en el espacio de vectorizar atributos, es decir, convertir atributos arbitrarios en índices en un vector o matriz.​​ Funciona aplicando una función hash a los atributos y usando los valores hash como índices directamente, en lugar de buscar los índices en una matriz asociativa .

Este método se atribuye a menudo a Weinberger y otros. (2009),​ pero existe una descripción mucho anterior de este método publicada por John Moody en 1989.​

Para más información

Ejemplo

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 bolsa de palabras (BOP): los componentes léxicos individuales se extraen y cuentan y cada componente léxico distinto en el conjunto de formación define un atributo (variable independiente) de cada uno de los documentos tanto en el conjunto de formación como en el de prueba.

Sin embargo, los algoritmos de aprendizaje automático (AA) suelen definirse en términos de vectores numéricos. Por lo tanto, las bolsas de palabras para un conjunto de documentos se consideran una matriz atributo-documento donde cada fila es un solo documento y cada columna es un solo atributo/palabra; la entrada i, j en dicha matriz captura la frecuencia (o peso) del j 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. ) Normalmente, estos vectores son extremadamente escasos, según la ley de Zipf .

El método común es construir, en el momento del aprendizaje o antes, una representación de diccionario del vocabulario del conjunto de formación 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 Juan 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 pueden convertir a la matriz término-documento usando el diccionario

Término	Índice
Juan	1
gustos	2
a	3
mirar	4
películas	5
María	6
también	7
también	8
fútbol	9

(Se elimina 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 crecen en tamaño a medida que crece el conjunto de formación.​ Por el contrario, si el vocabulario se mantiene fijo y no se aumenta con un conjunto de formación cada vez mayor, un adversario puede intentar inventar palabras nuevas 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! La investigación intentó utilizar funciones hash para los filtros de basura.​

Ten en cuenta que el método de hash no se limita a la clasificación de texto y tareas similares a nivel del documento, sino que se puede aplicar a cualquier problema que involucre un gran número (quizás ilimitado) de atributos.

Razones matemáticas

Matemáticamente, una ficha es un elemento $t$ en un conjunto finito (o contablemente infinito) $T$ . Supongamos que solo necesitamos procesar un cuerpo finito, entonces podemos poner todos los componentes léxicos que aparecen en el cuerpo en $T$, significa que $T$ es finito. Sin embargo, supongamos que queremos procesar todas las palabras posibles formadas por letras en castellano, entonces $T$ es contablemente infinito.

La mayoría de las redes neuronales solo pueden operar con entradas de vectores 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$, podemos usar codificación one-hot para mapearlo en $\mathbb {R} ^{n}$ . Primero, enumerar arbitrariamente $T=\{t_{1},t_{2},..,t_{m}\}$, luego define $\phi (t_{i})=e_{i}$ . En otras palabras, asignamos un índice único. $i$ a cada componente léxico, luego asigna el componente léxico con el índice $i$ al vector base unitario $e_{i}$ .

La codificación one-hot es fácil de interpretar, pero requiere mantener la enumeración arbitraria de $T$ . dado una ficha $t\in T$, calcular $\phi (t)$, debemos averiguar el índice $i$ de la ficha $t$ . Así, para implementar $\phi$ eficientemente, necesitamos una biyección rápida de calcular $h:T\to \{1,...,m\}$ y tenemos $\phi (t)=e_{h(t)}$ .

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

En la práctica, no hay una forma sencilla de construir un sistema de inyección eficiente. $h:T\to \{1,...,n\}$ . Sin embargo, no necesitamos una inyección estricta, sino una inyección aproximada. Como cuando $t\neq t'$, probablemente deberíamos tener $h(t)\neq h(t')$, por lo que probablemente $\phi (t)\neq \phi (t')$ .

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

Algoritmos

Hashing de atributos (Weinberger y otros 2009)

El algoritmo hash de atributos básico presentado en (Weinberger y otros, 2009)​ se define de la siguiente manera.

Primero, se especifican dos funciones hash: el hash del núcleo $h:T\to \{1,2,...,n\}$, y el signo hash $\zeta :T\to \{-1,+1\}$ . Luego, se define la función hash de atributos:$$\phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}$$Finalmente, extiende esta función de hash de atributos a cadenas de componentes léxicos 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 consisten de componentes léxicos en $T$. De manera 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 sobre la propiedad geométrica de $\phi$, pero $T$, por sí solo, es un conjunto de componentes léxicos, no podemos imponerle una estructura geométrica excepto la topología discreta, que es generada por la métrica discreta . Para que quede más bonito, lo llevamos a $T\to \mathbb {R} ^{T}$ y luego $\phi$ de $\phi :T\to \mathbb {R} ^{n}$ a $\phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}$ 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, que debe ser manejada de inmediato. Básicamente, sólo hay dos formas de manejar los infinitos. Se puede imponer una métrica y luego completarla para permitir sumas infinitas que se comporten bien, o se puede exigir que nada sea realmente infinito, sólo potencialmente . Aquí, optamos por el camino del potencial infinito, restringiendo $\mathbb {R} ^{T}$ contener sólo vectores con soporte finito : $\forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}$, sólo un número finito de entradas de $(x_{t})_{t\in T}$ son distintos de cero. Definir un producto interno en $\mathbb {R} ^{T}$ de la manera 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 de pie de página, si $T$ es infinito, entonces el espacio del producto interno $\mathbb {R} ^{T}$ no está completo . Completarlo nos llevaría a un espacio de Hilbert, que permite sumas infinitas con buen comportamiento. Ahora tenemos un espacio de producto interno, con estructura suficiente para describir la geometría de la función hash de atributos. $\phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}$ .

Primero, podemos ver por qué $h$ se llama "hash del núcleo": nos permite definir un núcleo $K:T\times T\to \mathbb {R}$ por$$K(t,t')=\langle e_{h(t)},e_{h(t')}\rangle$$En el lenguaje del "método del núcleo", $K$ es el kernel generado por el «mapa de atributos»$$\varphi :T\to \mathbb {R} ^{n},\quad \varphi (t)=e_{h(t)}$$Ten en cuenta que este no es el mapa de atributos que estábamos usando, que es $\phi (t)=\zeta (t)e_{h(t)}$ . De hecho, hemos estado usando otro núcleo. $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 núcleo $h$ con el hash binario $\zeta$ es el siguiente teorema, que establece que $\phi$ es una isometría "en promedio".

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

 

La declaración anterior interpreta la función hash binaria. $\zeta$ no como una función determinista de tipo $T\to \{-1,+1\}$, sino 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 declaración y prueba rigurosas, ver​

Implementación de pseudocódigo

En lugar de mantener un diccionario, un vectorizador de atributos que utiliza el método 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.

 function hashing_vectorizer(atributos: array of string, N : integer):
   x := new vector[N]
   for f in features:
     h := hash(f)
     x[h mod N] += 1
   return x

Por lo tanto, si el vector de atributos 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 atributos de salida (N ) para ser 4. Luego salidax 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.​ Si se utiliza dicha función hash, el algoritmo se convierte en

 function hashing_vectorizer(atributos: array of string, N : integer):
   x := new vector[N]
   for f in atributos:
     h := hash(f)
     idx := h mod N
     if ξ(f) == 1:
       x[idx] += 1
     else:
       x[idx] -= 1
   return x

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

Extensiones y variaciones

Hash de atributos aprendidos

El hash de única generalmente sufre una 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 con palabras con atributos hash tendría 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 simplemente ignorar el caso raro y pretender que todo $v$ medio $t$ . Sin embargo, si ambos son comunes, la degradación puede ser grave.

Para controlar esto, se pueden formar funciones hash supervisadas que eviten asignar componentes léxicos comunes a los mismos vectores de atributos.​

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 atributos no tiene por qué tener un efecto adverso en el rendimiento de la clasificación, incluso sin la función hash con signo.​

Weinberger y otros (2009) aplicaron su versión de hash de atributos al aprendizaje multitarea y, en particular, al filtrado de correo basura, donde los atributos de entrada son pares (usuario, atributos) de modo que un único vector de parámetros captura los filtros de basura por usuario, así como un filtro global para varios cientos de miles de usuarios y descubrió que la precisión del filtro aumentó.​

Chen y otros (2015) combinaron la idea de hash de atributos y 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 así representar una matriz como un vector en $\mathbb {R} ^{m}$, no importa que tan grande $n$ es. Con matrices virtuales, construyeron HashedNets, que son redes neuronales grandes, que ocupan sólo cantidades pequeñas de almacenamiento.​

Implementaciones

Las implementaciones del método de hash están presentes en:

• Mahout apache​
• gensim​
• aprendizaje de ciencias​
• sofía-ml​
• wabbit vocal
• Chispa Apache​
• R​
• TensorFlow​
• Dask-ML​

Véase también

• Método Kernel
• Aprendizaje por diccionarios dispersos

Enlaces externos

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