Cuantificación vectorial

Cuantización vectorial (VQ) es una técnica clásica de cuantificación a partir del procesamiento de señales que permite modelar funciones de densidad de probabilidad mediante la distribución de vectores prototipo. Originalmente se utilizó para la compresión de datos. Funciona dividiendo un gran conjunto de puntos (vectores) en grupos que tienen aproximadamente el mismo número de puntos más cercanos a ellos. Cada grupo está representado por su punto centroide, como en k-means y algunos otros algoritmos de agrupación.

La propiedad de coincidencia de densidad de la cuantificación vectorial es poderosa, especialmente para identificar la densidad de datos grandes y de alta dimensión. Dado que los puntos de datos están representados por el índice de su centroide más cercano, los datos que ocurren comúnmente tienen un error bajo y los datos raros tienen un error alto. Esta es la razón por la que VQ es adecuado para la compresión de datos con pérdida. También se puede utilizar para la corrección de datos con pérdida y la estimación de densidad.

La cuantificación vectorial se basa en el paradigma de aprendizaje competitivo, por lo que está estrechamente relacionada con el modelo de mapa autoorganizado y con los modelos de codificación dispersa que se usan en los algoritmos de aprendizaje profundo, como el codificador automático.

Entrenamiento

El algoritmo de entrenamiento más simple para la cuantificación de vectores es:

1. Escoge un punto de muestra al azar
2. Mueva el centroide vector de cuantificación más cercano hacia este punto de muestra, por una pequeña fracción de la distancia
3. Repito

Un algoritmo más sofisticado reduce el sesgo en la estimación de coincidencia de densidad y garantiza que se utilicen todos los puntos, al incluir un parámetro de sensibilidad adicional:

1. Aumentar la sensibilidad de cada centroide si{displaystyle S_{i} por una pequeña cantidad
2. Escoge un punto de muestra P{displaystyle P} al azar
3. Para cada cuantización vectorial centroid ci{displaystyle C_{i}, vamos d()P,ci){displaystyle d(P,c_{i})} denota la distancia P{displaystyle P} y ci{displaystyle C_{i}
4. Encontrar el centroide ci{displaystyle C_{i} para la cual d()P,ci)− − si{displaystyle d(P,c_{i})-s_{i} es el más pequeño
5. Muévanse. ci{displaystyle C_{i} hacia P{displaystyle P} por una pequeña fracción de la distancia
6. Set si{displaystyle S_{i} a cero
7. Repito

Es deseable utilizar un programa de enfriamiento para producir convergencia: consulte Recocido simulado. Otro método (más simple) es LBG, que se basa en K-Means.

El algoritmo se puede actualizar iterativamente con 'live' datos, en lugar de elegir puntos aleatorios de un conjunto de datos, pero esto introducirá cierto sesgo si los datos se correlacionan temporalmente en muchas muestras.

Aplicaciones

La cuantificación vectorial se utiliza para la compresión de datos con pérdida, la corrección de datos con pérdida, el reconocimiento de patrones, la estimación de densidad y la agrupación.

La corrección o predicción de datos con pérdida se utiliza para recuperar los datos que faltan en algunas dimensiones. Se realiza encontrando el grupo más cercano con las dimensiones de datos disponibles y luego prediciendo el resultado en función de los valores de las dimensiones que faltan, asumiendo que tendrán el mismo valor que el centroide del grupo.

Para la estimación de densidad, el área/volumen que está más cerca de un centroide en particular que de cualquier otro es inversamente proporcional a la densidad (debido a la propiedad de coincidencia de densidad del algoritmo).

Uso en compresión de datos

Cuantificación de vectores, también llamada "cuantificación de bloques" o "cuantización de coincidencia de patrones" se utiliza a menudo en la compresión de datos con pérdida. Funciona codificando valores de un espacio vectorial multidimensional en un conjunto finito de valores de un subespacio discreto de dimensión inferior. Un vector de espacio inferior requiere menos espacio de almacenamiento, por lo que los datos se comprimen. Debido a la propiedad de coincidencia de densidad de la cuantificación vectorial, los datos comprimidos tienen errores que son inversamente proporcionales a la densidad.

La transformación generalmente se realiza por proyección o usando un libro de códigos. En algunos casos, también se puede usar un libro de códigos para codificar en entropía el valor discreto en el mismo paso, generando un valor codificado de longitud variable codificado con prefijo como su salida.

El conjunto de niveles de amplitud discreta se cuantifica conjuntamente en lugar de cada muestra que se cuantifica por separado. Considerar un k-dimensional vector [x1,x2,...,xk]{displaystyle [x_{1},x_{2},...,x_{k} de niveles de amplitud. Se comprime eligiendo el vector más cercano de un conjunto de n- vectores dimensionales [Sí.1,Sí.2,...,Sí.n]{displaystyle Sí., con n. k.

Todas las posibles combinaciones de las n-dimensional vector [Sí.1,Sí.2,...,Sí.n]{displaystyle Sí. forman el espacio vectorial al que pertenecen todos los vectores cuantificados.

Solo se envía el índice de la palabra clave en el libro de códigos en lugar de los valores cuantificados. Esto ahorra espacio y logra más compresión.

La cuantificación de vector doble (VQF) es parte del estándar MPEG-4 que se ocupa de la cuantificación de vector intercalado ponderado en el dominio del tiempo.

Códecs de vídeo basados en cuantificación vectorial

• Bink video
• Cinepak
• Daala está basada en la transformación, pero utiliza la cuantificación vectorial de pirámide en coeficientes transformados
• Video interactivo digital: Video de producción y video en tiempo real
• Indeo
• Microsoft Video 1
• QuickTime: Apple Video (RPZA) y Graphics Codec (SMC)
• Sorenson SVQ1 y SVQ3
• Smacker video
• VQA formato, utilizado en muchos juegos

El uso de códecs de video basados en cuantificación vectorial ha disminuido significativamente a favor de aquellos basados en predicción compensada de movimiento combinados con codificación de transformación, p. los definidos en los estándares MPEG, ya que la baja complejidad de decodificación de la cuantificación vectorial se ha vuelto menos relevante.

Códecs de audio basados en cuantificación vectorial

• AMR-WB+
• CELP
• Codec 2
• DTS
• G.729
• iLBC
• Ogg Vorbis
• Opus está basado en la transformación, pero utiliza la cuantificación vectorial de pirámide en coeficientes transformados
• TwinVQ

Uso en el reconocimiento de patrones

VQ también se usó en los años ochenta para el reconocimiento del habla y del hablante. Recientemente también se ha utilizado para la búsqueda eficiente de vecinos más cercanos. y reconocimiento de firma en línea. En aplicaciones de reconocimiento de patrones, se construye un libro de códigos para cada clase (siendo cada clase un usuario en aplicaciones biométricas) usando vectores acústicos de este usuario. En la fase de prueba se calcula la distorsión de cuantificación de una señal de prueba con todo el conjunto de libros de códigos obtenidos en la fase de entrenamiento. El libro de códigos que proporciona la distorsión de cuantificación vectorial más pequeña indica el usuario identificado.

La principal ventaja de VQ en el reconocimiento de patrones es su baja carga computacional en comparación con otras técnicas como la deformación dinámica del tiempo (DTW) y el modelo oculto de Markov (HMM). El principal inconveniente frente a DTW y HMM es que no tiene en cuenta la evolución temporal de las señales (voz, firma, etc.) porque se mezclan todos los vectores. Para superar este problema, se ha propuesto un enfoque de libro de códigos de múltiples secciones. El enfoque multisección consiste en modelar la señal con varias secciones (por ejemplo, un libro de códigos para la parte inicial, otro para el centro y un último libro de códigos para la parte final).

Usar como algoritmo de agrupación

Como VQ busca centroides como puntos de densidad de muestras cercanas, también se puede usar directamente como un método de agrupamiento basado en prototipos: cada centroide se asocia con un prototipo. Con el objetivo de minimizar el error de cuantización al cuadrado esperado e introducir una ganancia de aprendizaje decreciente que cumple las condiciones de Robbins-Monro, múltiples iteraciones sobre todo el conjunto de datos con un número concreto pero fijo de prototipos convergen en la solución del algoritmo de agrupamiento de k-means de forma incremental. conducta.

Redes adversarias generativas (GAN)

VQ se ha utilizado para cuantificar una capa de representación de características en el discriminador de redes antagónicas generativas. La técnica de cuantificación de características (FQ) realiza una coincidencia de características implícita. Mejora el entrenamiento GAN y produce un rendimiento mejorado en una variedad de modelos GAN populares: BigGAN para generación de imágenes, StyleGAN para síntesis facial y U-GAT-IT para traducción de imagen a imagen sin supervisión.