Hai bisogno di compressione?

Hai bisogno di compressione?

Una implementazione più efficiente della classificazione dei temi basata sulla compressione

L’articolo recentemente pubblicato dal titolo “Classificazione del testo a risorse ridotte: un metodo di classificazione senza parametri con compressori [1]” ha attirato molta attenzione pubblica nei giorni scorsi. La loro scoperta chiave è che in alcuni casi possono superare modelli di linguaggio di grandi dimensioni come BERT utilizzando l’idea semplice che due documenti di testo sono più simili se possono essere compressi in un file di dimensioni più piccole (anche se c’è una certa controversia sulla validità dei loro risultati, vedere questo post del blog e questa discussione che include la risposta dell’autore).

L’idea principale alla base del loro approccio è che la “distanza delle informazioni” tra due documenti, come definita da Bennet et al. [2], è una buona metrica di distanza da utilizzare durante la classificazione del testo. Poiché la distanza delle informazioni stessa non è calcolabile, la approssimano utilizzando la Distanza di Compressione Normalizzata (NCD) [3], che stima la distanza delle informazioni utilizzando compressori di dati “reali” come gzip. La NCD ha la proprietà che i compressori migliori (cioè i compressori con un rapporto di compressione migliore) consentiranno una migliore stima della vera distanza delle informazioni.

Sembra quindi naturale aspettarsi che un miglior compressore raggiunga prestazioni superiori nella classificazione. Ma non possono convalidare questo sperimentalmente; il miglior compressore considerato nell’articolo, bz2, ha prestazioni peggiori in termini di precisione rispetto a gzip. Spiegano ciò nel seguente modo: “[…] l’algoritmo di Burrows-Wheeler utilizzato da bz2 elimina l’informazione dell’ordine dei caratteri permutando i caratteri durante la compressione” [1, p.6817]. Ciò implica che la compressione da sola non spiega le loro scoperte, ma che ha qualcosa a che fare anche con l’ordine dei caratteri.

Questo mi ha fatto chiedere: quanto dei loro risultati è dovuto alla compressione e quanto è dovuto al confronto delle stringhe tra due documenti?

• Come automatizzare la qualità del codice con gli hook pre-commit di Python
• Crea un bot di domanda e risposta trasparente per i tuoi documenti con LangChain e GPT-3
• Ultima DXA-nazione

Per indagare su questa domanda, confronto i loro risultati con due alternative: (1) un semplice compressore che si basa esclusivamente sulla sostituzione di stringhe ricorrenti e (2) un algoritmo che effettua esplicitamente il confronto delle sottostringhe tra un documento di query e tutti i documenti appartenenti a un certo argomento.

Una prima ablazione: riuscirà LZ4 a fare il lavoro? L’algoritmo di compressione gzip si basa su DEFLATE, che a sua volta utilizza LZ77 e la codifica di Huffman per comprimere i dati. Vediamo questi due algoritmi in modo più dettagliato e pensiamo a cosa implicano quando vengono applicati al nostro caso d’uso.

Durante la compressione, LZ77 utilizza una finestra scorrevole sui dati precedentemente visti. Se una stringa di caratteri viene ripetuta, invece della stringa stessa viene memorizzato un riferimento alla prima occorrenza della stringa di caratteri. Pertanto, se prendiamo la lunghezza di due documenti concatenati come metrica di distanza, i documenti saranno più vicini se hanno più sottostringhe sovrapposte entro la dimensione della finestra scorrevole (tipicamente 32KB).

La codifica di Huffman comprime ulteriormente il testo risultante: invece di utilizzare 8 bit per ogni carattere, rappresenta quelle lettere che si verificano frequentemente con meno bit e quelle lettere che si verificano raramente con più bit. Se applichiamo la codifica di Huffman ai documenti concatenati, due documenti sarebbero più piccoli dopo la compressione se utilizzano i caratteri con frequenza simile.

Si potrebbe pensare che le sottostringhe corrispondenti siano molto più importanti per la classificazione dei temi rispetto alle frequenze dei caratteri simili. Pertanto, eseguo uno studio di ablazione analizzando le prestazioni quando utilizzo l’algoritmo LZ4 [4] per la compressione (essenzialmente LZ77 ma con un’implementazione veloce disponibile in python). Poiché LZ4 ha un rapporto di compressione molto più basso rispetto a gzip, la loro spiegazione suggerirebbe che le prestazioni di LZ4 sono peggiori di gzip. Tuttavia, se la cosa principale che sta accadendo è il confronto delle sottostringhe, LZ4 si comporterà altrettanto bene come gzip.

Un algoritmo più esplicito Per andare ancora oltre, implemento un semplice algoritmo che effettua esplicitamente il confronto delle sottostringhe: assegna i documenti all’argomento con le sottostringhe più simili (le sottostringhe sono n-grammi a livello di caratteri qui). Funziona nel seguente modo:

Codifica del testo:1. Estrarre tutti gli n-grammi di caratteri all’interno del testo con 5 ≤ n ≤ 50.2. Per gli n-grammi estratti, calcolare un codice hash a 8 cifre utilizzando `hash(n_gram) % int(10e8)` in python (poiché voglio controllare quante cose diverse tenere traccia).3. Tenere traccia di questo in insiemi (perdendo così l’informazione su quante volte si verifica un dato codice).

Addestramento:1. Calcola l’insieme di codici hash per ogni testo di un determinato argomento.2. Prendi l’unione degli insiemi per ottenere un insieme di codici hash che si verificano nell’argomento.

Inferenza:1. Per qualche testo di interrogazione, calcola l’insieme dei suoi n-grammi hashati.2. Per ogni argomento incontrato durante l’addestramento, calcola la dimensione dell’intersezione tra gli insiemi dell’argomento e l’insieme di interrogazione.3. Assegna il testo di interrogazione all’argomento con la maggiore intersezione.

Esperimento e RisultatiConfronto i risultati di gzip, lz4 e l’algoritmo degli n-grammi hashati nell’impostazione a 100 prove con 5 esecuzioni, come descritto nel loro articolo. Per tutti e tre i metodi mi attengo alla loro configurazione sperimentale al fine di riprodurre i loro risultati riportati (ancora una volta, lasciandoci con misure di accuratezza potenzialmente sovrastimate). Il codice può essere trovato su GitHub.

Puoi vedere le prestazioni su tre set di dati da torchtext (AG_NEWS [5], DBpedia [6] e YahooAnswers [5]) nella seguente tabella:

Vediamo che lz4 e gli n-grammi hashati superano gzip su tutti e tre i set di dati considerati, con l’algoritmo degli n-grammi hashati che è il migliore in 2 su 3 dati. Ma non compete ancora con BERT, che ha una performance del 0,82 su AG_NEWS e vicina a 1 su DBpedia secondo il loro articolo nell’impostazione a 100 prove.

Questi risultati hanno importanti implicazioni pratiche: nel nostro esperimento, l’algoritmo basato su lz4 viene eseguito approssimativamente 10 volte più velocemente dell’algoritmo basato su gzip. E ancor più importante, l’algoritmo degli n-grammi hashati migliora anche la complessità computazionale al momento dell’inferenza: invece di dover confrontare un documento di interrogazione con ogni altro documento nel corpus di testo, devi solo confrontarlo con ogni insieme di argomenti.

Cosa impariamo da questo?I miei risultati suggeriscono che la forza trainante dietro l’impressionante performance riportata di gzip può essere attribuita al fatto che il loro metodo confronta implicitamente gli n-grammi a livello di carattere tra i documenti. Questa scoperta consente l’utilizzo di compressori più veloci come lz4 senza alcuna perdita di prestazioni. Inoltre, si può persino riscrivere il loro algoritmo per avere complessità costante rispetto alla dimensione del dataset al momento dell’inferenza, avvicinando così il loro metodo all’uso pratico su grandi set di dati. Se vuoi utilizzarlo nella pratica, ho iniziato a implementare il mio algoritmo proposto seguendo l’API di scikit-learn qui.

L’unica domanda che rimane è: perché questo supera l’approccio TF-IDF che confronta anche le parole tra i documenti?

Probabilmente considerare gli n-grammi a livello di carattere svolge un lavoro migliore per alcuni compiti rispetto alla suddivisione del testo in singole parole. Ma probabilmente, ancora più importante, il metodo qui conferisce uguale importanza a tutti gli n-grammi, indipendentemente dal loro conteggio di occorrenze. Ciò significa che attribuisce molta importanza alle cosiddette informazioni a lunga coda (leggere: rare), che apparentemente sono rilevanti per alcuni compiti di testo come la rilevazione degli argomenti. Nota che le reti dei trasformatori non svolgono un buon lavoro nel modellare tali informazioni a lunga coda (come evidenziato ad esempio [5]), motivo per cui questi approcci molto semplici sono un benchmark molto interessante per valutare il tuo modello a milioni di parametri.

Riferimenti[1] Z. Jiang, M. Yang, M. Tsirlin, R. Tang, Y. Dai, J. Lin. “Classificazione di testi a bassa risorsa: un metodo di classificazione senza parametri con compressori (2023)”, ACL 2023[2] C. H. Bennett, P. Gács, M. Li, P. MB Vitányi e W. H. Zurek, Distanza di informazione (1998), IEEE Transactions on information theory[3] M. Li, X. Chen, X. Li, B. Ma e P. Vitányi, La metrica di similarità (2004), IEEE transactions on Information Theory[4] N. Kandpal, H. Deng, A. Roberts, E. Wallace, C. Raffel, Grandi modelli linguistici faticano a imparare conoscenze a lunga coda (2022), arxiv.org/abs/2211.08411

Grazie a Joel Niklaus e Marcel Gygli per le nostre discussioni e il vostro feedback.