Vector Quantization

Vektorquantisierung (VQ) ist ein Kompressionsverfahren, bei dem jeder Vektor in einem Datensatz durch den Index des nächstgelegenen Eintrags in einer kleinen Menge repräsentativer Vektoren, dem sogenannten Codebuch, ersetzt wird. Beim Kodieren wird nur der Index gespeichert, beim Dekodieren wird der Index nachgeschlagen. Der Rekonstruktionsfehler entspricht dem Abstand zwischen dem ursprünglichen Vektor und seinem Codewort. Ein Codebuch mit K Einträgen benötigt unabhängig von der Anzahl der Dimensionen des Vektors log₂(K) Bits pro Vektor. Ein Codebuch mit 256 Einträgen speichert daher jeden Vektor in einem Byte. VQ stammt aus der Signalverarbeitung: Stuart Lloyds Algorithmus von 1957 aus den Bell Labs zur Entwicklung skalarer Quantisierer wurde 1982 veröffentlicht und wird heute üblicherweise k-means genannt. Yoseph Linde, Andrés Buzo und Robert Gray erweiterten den Algorithmus 1980 auf Vektoren. Im Deep Learning wurde VQ zum Standardverfahren, um Bilder, Audio und Video in diskrete Tokens für generative KI umzuwandeln.

So funktioniert Vektorquantisierung#

Ein Codebuch wird üblicherweise mit k-means-Clustering gelernt: Weise jeden Trainingsvektor dem nächstgelegenen Codewort zu, verschiebe jedes Codewort auf den Mittelwert der ihm zugewiesenen Vektoren und wiederhole den Vorgang. Dadurch steigt die durchschnittliche Verzerrung nie an. Die Farbquantisierung veranschaulicht den gesamten Ablauf anhand der Pixel eines Fotos mit dem Modul scipy.cluster.vq von SciPy:

import numpy as np
from scipy.cluster.vq import kmeans2, vq
from sklearn.datasets import load_sample_image

image = load_sample_image("china.jpg")  # 427 x 640 RGB photo bundled with scikit-learn
pixels = image.reshape(-1, 3).astype(np.float64)  # one 3-D color vector per pixel

# Learn a 16-entry codebook with k-means (Lloyd's algorithm) on a sample of pixels
rng = np.random.default_rng(0)
codebook, _ = kmeans2(rng.choice(pixels, 5000), 16, minit="++", seed=0)

# Encode: replace each pixel with the index of its nearest codeword (4 bits instead of 24)
indices, _ = vq(pixels, codebook)
# Decode: look each index up in the codebook
reconstruction = codebook[indices]

rmse = np.sqrt(((pixels - reconstruction) ** 2).mean())
print(f"{len(pixels):,} pixels, {len(codebook)} codewords, 24 -> 4 bits per pixel")
print(f"Reconstruction RMSE: {rmse:.1f} on the 0-255 scale")

Alle 273.280 Pixel werden als 4-Bit-Indizes in 16 Farben gespeichert. Das sind sechsmal weniger Farbdaten als bei 24-Bit-RGB, bei einem quadratischen Mittelwertfehler von 11,3 Intensitätsstufen von 255.

Skalare Quantisierung ist der eindimensionale Sonderfall, und die Modellquantisierung wendet sie auf neuronale Netze an. Ultralytics YOLO26 nutzt sie beim Export: quantize=8 rundet jedes Gewicht und jede Aktivierung einzeln auf einen von 256 ganzzahligen Werten. Die Aktivierungsbereiche werden in einem Kalibrierungsdurchlauf anhand der Bilder in data ermittelt. Die gemeinsame Quantisierung ganzer Vektoren nutzt die Korrelationen zwischen den Dimensionen aus. Bei derselben Bitrate hat ein optimaler Vektorquantisierer niemals eine höhere Verzerrung als ein optimaler skalarer Quantisierer, der auf jeden Wert einzeln angewendet wird.

Produkt- und Residualquantisierung#

Ein einzelnes Codebuch wächst mit dem Bitbudget exponentiell, denn für 64 Bits wären 2⁶⁴ Codewörter erforderlich. Die 2011 von Hervé Jégou, Matthijs Douze und Cordelia Schmid eingeführte Produktquantisierung teilt jeden Vektor in m Teilvektoren auf und quantisiert jeden davon mit einem eigenen Codebuch mit 256 Einträgen. Bei m = 8 schrumpft ein 128-dimensionales float32-Embedding von 512 Bytes auf 8 Bytes, und die Abstände zu einer Suchanfrage werden anhand kleiner Nachschlagetabellen berechnet. Die FAISS-Bibliothek von Meta kombiniert das Verfahren mit einem invertierten Dateiindex, einem groben k-means-Quantisierer, der jede Suchanfrage auf wenige Cluster beschränkt. So wird eine Vektorsuche im Milliardenmaßstab möglich.

Bei der Residualquantisierung werden Codebücher stattdessen gestapelt: Das zweite Codebuch quantisiert den Fehler, den das erste hinterlässt, das dritte den Fehler des zweiten und so weiter. Die neuronalen Audiocodecs SoundStream von Google (2021) und EnCodec von Meta (2022) komprimieren damit Sprache und Musik auf wenige Kilobit pro Sekunde. Visuelle autoregressive Modellierung (VAR) wendet das Verfahren über verschiedene Bildauflösungen hinweg an.

VQ-VAE und Bild-Tokens#

Aäron van den Oord, Oriol Vinyals und Koray Kavukcuoglu von DeepMind stellten VQ-VAE 2017 in Neural Discrete Representation Learning vor. Die Encoder-Ausgabe eines Autoencoders wird an jeder räumlichen Position durch das nächstgelegene Codewort ersetzt, und der Decoder rekonstruiert die Eingabe aus den Codewörtern. Für die Suche nach dem nächsten Nachbarn gibt es keinen Gradienten. Daher leitet ein Straight-Through-Schätzer während der Rückpropagierung den Gradienten des Decoders daran vorbei. In PyTorch wird dies als z_q = z + (z_q - z).detach() geschrieben. Zwei zusätzliche Verlust-Terme ziehen die Codewörter zu den Encoder-Ausgaben und sorgen dafür, dass sich der Encoder auf seine ausgewählten Codewörter festlegt. Im Paper wird der zweite Term mit 0,25 gewichtet.

Die resultierenden Token-Raster speisen ein zweites Modell, meist einen Transformer, der lernt, sie zu erzeugen. VQGAN (2021) ergänzte adversariale und perzeptuelle Verluste, um schärfere Tokens zu erzeugen, und wurde zum Tokenizer zahlreicher Text-zu-Bild-Modelle. Ein häufiges Problem ist der Kollaps des Codebuchs: Die meisten Codewörter werden nie ausgewählt, wodurch das effektive Vokabular schrumpft. Initialisierung mit k-means, Aktualisierungen des Codebuchs anhand gleitender Mittelwerte und das Zurücksetzen ungenutzter Codes wirken dem entgegen. Googles finite skalare Quantisierung (FSQ, 2023) vermeidet das Problem, indem einige wenige latente Dimensionen jeweils auf eine Handvoll fester Stufen gerundet werden. So ist jeder Code im impliziten Codebuch erreichbar.

Vektorquantisierung im Vergleich zu verwandten Begriffen#

• Vektordatenbanken: Speichern und indexieren Embeddings und wenden intern oft Produktquantisierung an, damit diese in den Arbeitsspeicher passen.
• Dimensionsreduktion: Bildet Vektoren auf weniger kontinuierliche Dimensionen ab, wie es PCA tut. VQ bildet dagegen jeden Vektor auf einen diskreten Code ab.
• Tokenisierung: Zerlegt Text in Einheiten aus einem festen Vokabular. VQ erstellt ein entsprechendes Vokabular für kontinuierliche Signale wie Bildausschnitte und Audio-Frames.