Hashing de funciones para el procesamiento de funciones de datos.

1. Introducción a las técnicas de hashing/hashing de funciones.

El requisito de entrada de la mayoría de los algoritmos de aprendizaje automático es una matriz real. La conversión de datos originales en una matriz real se denomina ingeniería de características (también llamada técnica de hash). Su objetivo es convertir un punto de datos en un vector.

Veamos primero los métodos generales de ingeniería de características para datos categóricos y datos de texto.

Una variable categórica es un conjunto de variables con un número limitado de valores. Como número de identificación, categoría de publicidad, etc. La forma más común de manejar variables categóricas es utilizar codificación de un solo paso: crear variables binarias NN, donde NN son todos los valores posibles de la variable categórica.

Para el procesamiento de características de datos de texto, el método más simple es el modelo de bolsa de palabras: cree variables binarias NN, donde n es el número de palabras (es decir, el número de palabras diferentes). Para cada documento, se crea un vector NN-dimensional y el número de palabras contenidas en el documento es el valor de índice correspondiente a la palabra en este vector.

Se puede ver que estos dos métodos son muy similares, ambos crean matrices dispersas de alta dimensión. El hash de características es una tabla hash que implementa estos dos métodos de conversión. Aquí hay una breve introducción a las tablas hash.

2. Hash Table

Hashtable es una estructura de datos que accede directamente a las ubicaciones de almacenamiento de memoria en función de claves. Cada tabla hash utiliza una función hash (también llamada función hash) para asignar pares clave-valor. Esta función puede comprimir cualquier tipo de datos o mensaje en un resumen (es decir, valor hash), lo que reduce el volumen de datos y fija el formato. La función hash ideal dividirá diferentes claves en diferentes bloques, pero la mayoría de las tablas hash tienen la posibilidad de colisión hash, es decir, diferentes claves se pueden asignar al mismo valor (se explicará más adelante, esto no afectará el rendimiento de la máquina). modelo de aprendizaje).

Cuando utilizamos tablas hash, normalmente necesitamos definir el rango de salida. Por ejemplo, si queremos definir el rango de salida entre 0 y n, entonces podemos usar una función para convertir los datos de entrada en el rango [0, n-1]. Supongamos que creamos la siguiente función hash, que asigna palabras a cinco categorías, es decir, 0-4 índices:

La tabla hash tiene las siguientes características:

Es posible la misma entrada Tener la misma salida (en general, la proporción no es alta)

Diferentes salidas deben corresponder a diferentes entradas.

El cálculo directo es fácil, pero el cálculo inverso es difícil.

Encuentra la salida en función de la entrada, lo cual es muy eficiente.

3. Un caso sencillo

Tomamos como ejemplo la detección de spam (spam) (una aplicación de clasificación de texto).

Supongamos que hay dos correos electrónicos como los siguientes, el primero es spam y el segundo no es spam:

¡Gano $10,000 a la semana solo navegando por la web! (spam)

¿Estás disponible para una reunión a principios de la próxima semana? (No spam)

Marca: 1

Diez: Dos

Mil: 3

Dólares: 4

por: 5

Semana 6

Justo ahora: 7

Navegar: 8

Número 9

Sitio web: 10

Respectivamente: 11

Tú: 12

Número gratuito: 13

Aplicable a: 14

Respuesta: 15

Reunión: 16

Mañana: 17

Siguiente: 18

El vocabulario total es * * *19, creamos un vector de 19 dimensiones y obtenemos el siguiente resultado:

¡Puedo ganar diez mil dólares a la semana sólo navegando por Internet! (spam)

- gt;[1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]

Puedes asistir a uno a principios de la próxima semana ¿Reunión? (no spam)

->[0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0]

Entonces podemos usar el modelo de clasificación para entrenar , predecir, etiquetar spam y filtrar spam. Sin embargo, existe una forma muy sencilla de evitar este escrutinio, como enviar un correo electrónico como este:

¿Estás disponible para una reunión en línea a principios de la próxima semana?

- gt; 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0]

Este correo electrónico contiene algunas palabras creadas por el usuario que no están en nuestro vocabulario pero que son ciertas. Aún así podemos identificarlo como spam. Sin embargo, el resultado de la conversión con el modelo de bolsa anterior es un vector similar al segundo correo electrónico anterior. Obviamente, el modelo de clasificación clasificará esto como un correo electrónico normal. Por lo tanto, los proyectos característicos mencionados anteriormente obviamente no pueden cumplir con los requisitos.

Además, existe un gran problema con el uso de los métodos de ingeniería de características descritos anteriormente, que es que a menudo se crean vectores dispersos de muy altas dimensiones. Supongamos que tenemos 654,38 millones de correos electrónicos como conjunto de entrenamiento. Cada correo electrónico tiene solo unas pocas docenas de palabras en promedio, pero el vocabulario puede ser de cientos de miles. Los datos de entrada creados de esta manera son una matriz dispersa de alta dimensión, que no es una entrada amigable para muchos algoritmos de aprendizaje automático.

Si utiliza el método de función hash anterior, todos los datos originales se pueden convertir en valores hash dentro del rango especificado. Esto tiene varias ventajas:

Incluso para palabras que no están en el vocabulario, aún podemos calcular un valor hash, que no se puede eludir fácilmente y no requiere preparar el vocabulario con anticipación. La conversión de nuevas funciones no afecta la longitud de las funciones de entrada (porque el rango hash ya está definido de antemano).

Solo necesita aplicar hash a los datos nuevos, no es necesario aplicar hash a todos los datos, por lo que admite el aprendizaje en línea.

Después de la ingeniería de características hash, los vectores que originalmente eran muy escasos pueden volverse menos escasos.

Aunque existen colisiones de hash, la investigación y la práctica muestran que el impacto es muy pequeño.

El mayor inconveniente de la ingeniería de funciones hash es la falta de interpretabilidad, ya que la función se trata como un hash no interpretable. Sin embargo, esta técnica puede resultar muy útil en muchas situaciones.

Consejos para usar funciones hash

Al usar funciones hash, debes elegir el rango de hash y no existe un estándar unificado para esto. Los rangos de hash más pequeños provocarán más colisiones y afectarán la precisión, mientras que los rangos más grandes ocuparán más memoria y requerirán más tiempo de entrenamiento. Entonces, en situaciones reales, debes elegir en función de tus objetivos. Si el tiempo de entrenamiento no es una preocupación, considere utilizar una gama más amplia de resultados de hash.