Fast Exact Nearest-Neighbor Learning for High-Frequency Financial Time Series

Sintesi Tecnica: Apprendimento Rapido e Esatto dei Vicini Più Vicini per Serie Temporali Finanziarie ad Alta Frequenza

Definizione del Problema
L'IA finanziaria sta entrando in un'era di scalabilità in cui i modelli devono ingerire enormi corpora storici (azioni, ETF, FX, opzioni) per supportare il trading in tempo reale, la gestione del rischio e la determinazione dei prezzi dei derivati. Un collo di bottiglia critico esiste nell'attuale stack tecnologico: mentre gli strumenti basati su Python (NumPy, scikit-learn) offrono flessibilità, essi soffrono di overhead dell'interprete, saturazione della larghezza di banda della memoria e scarsa località del cache, quando si interrogano centinaia di migliaia di stati storici. Al contrario, le soluzioni in C++ e FPGA offrono velocità ma creano un divario "dalla ricerca alla produzione" a causa della necessità di codebase separate e ottimizzazioni manuali. La sfida specifica affrontata è l'inferenza esatta del k-esimo vicino più vicino (KNN) per serie temporali ad alta frequenza, dove il costo lineare della ricerca brute-force ($O(n \cdot d)$) diventa proibitivo per i budget di latenza in tempo reale, sebbene i metodi approssimativi (come HNSW) sacrifichino l'esattezza richiesta da certe applicazioni finanziarie.

Metodologia
Gli autori propongono un k-d tree SIMD in Mojo progettato specificamente per corpora di serie temporali finanziarie. Mojo, un linguaggio di sistema compilato con sintassi compatibile con Python, consente la co-progettazione di algoritmo, layout di memoria e hardware senza abbandonare l'ecosistema Python. La metodologia integra tre ottimizzazioni core:

1. Suddivisione Basata sulla Varianza: Diversamente dalle suddivisioni standard basate sulla mediana, l'albero seleziona l'asse di divisione in base alla dimensione con la massima varianza ($j^* = \arg\max \text{Var}(\{x_{i,j}\})$). Questo concentra la potatura precoce sulle caratteristiche finanziarie più discriminanti (rendimenti, volatilità, momentum), creando sottoregioni più strette.
2. Archiviazione in Flat-Buffer Contiguo: I vettori di addestramento sono memorizzati in un flat buffer row-major ($X \in \mathbb{R}^{n \times d}$) indicizzato da un array permutato. I nodi foglia sono definiti da offset interi, permettendo ai candidati di essere letti come blocchi di memoria contigui. Ciò elimina l'overhead del pointer-chasing e garantisce l'allineamento della cache-line.
3. Kernel Vettorizzati al Tempo di Compilazione: I calcoli della distanza utilizzano la vettorizzazione SIMD (Single Instruction, Multiple Data). Il kernel è specializzato al tempo di compilazione (comptime) per dimensioni specifiche (ad esempio, $d=16$ o $d=24$) e larghezze SIMD, generando codice completamente srotolato (unrolled) e privo di scalari. La distanza euclidea al quadrato è decomposta in blocchi paralleli della larghezza dei registri.

Il sistema è stato valutato su otto dataset finanziari (azioni USA, ETF, FX) su due architetture hardware: x86 (Intel/AMD) e ARM64 (Apple M3). I confronti sono stati effettuati rispetto alle implementazioni brute-force e k-d tree di scikit-learn, nonché all'approccio brute-force SIMD di Mojo.

Contributi Chiave

1. Implementazione del k-d Tree SIMD in Mojo: Una nuova implementazione che combina la potatura basata sulla varianza, il layout di memoria flat-buffer e i kernel di distanza vettorizzati al tempo di compilazione per il KNN esatto su grandi dataset finanziari.
2. Analisi del Runtime Teorica: Una dimostrazione che, sotto le normali assunzioni di potatura, il k-d tree di Mojo domina asintoticamente sia il brute force SIMD di Mojo che il k-d tree di scikit-learn nel regime a stock fisso, grande-$n$ e dimensionalità moderata.
3. Co-Design Finanza-Hardware: Un approccio standardizzato di feature engineering dove le caratteristiche derivate da OHLCV sono allineate con le larghezze SIMD (16 e 24 valori float32 che mappano rispettivamente su 2 e 3 larghezze di registro), preservando l'interpretabilità finanziaria massimizzando al contempo il throughput.
4. Validazione Empirica: Benchmark completi che mostrano incrementi di velocità significativi attraverso diversi asset class e piattaforme hardware, con significatività statistica confermata tramite test Wilcoxon signed-rank.
5. Dimostrazione di Scalabilità: Un esperimento secondario utilizzando Extra Trees per il pricing della volatilità implicita (IV), mostrando che i guadagni di throughput consentono l'addestramento su 10$\times$ più dati, migliorando direttamente l'accuratezza della predizione.

Risultati

• Accelerazione su x86 ($d=16$): Il k-d tree di Mojo ha ottenuto un'accelerazione di 17,5–21,6$\times$ rispetto al k-d tree di scikit-learn e di 1,2–1,3$\times$ rispetto al brute force di scikit-learn su dataset che vanno da 143K a 277K campioni.
• Accelerazione su ARM64 ($d=24$): Il metodo ha ottenuto un'accelerazione di 28,1–43,5$\times$ rispetto al brute force di scikit-learn su Apple M3. Notevolmente, su ARM64, il kernel brute-force SIMD di Mojo era 780–1549$\times$ più lento del k-d tree a causa di un mismatch tra la larghezza SIMD al tempo di compilazione (ottimizzata per i registri a 256 bit di x86) e i registri nativi a 128 bit di ARM. Tuttavia, la potatura algoritmica del k-d tree ($O(n^{1-1/d})$) lo ha reso immune a questa penalità specifica dell'hardware, mantenendo enormi guadagni.
• Esponenti di Scalabilità: L'adattamento empirico della complessità del runtime $T(n) = Cn^\alpha$ ha prodotto un esponente di 1,755 per il k-d tree di Mojo (solo query), rispetto a 1,885 per il brute force e 2,320 per il k-d tree di scikit-learn. Ciò conferma una scalabilità sub-quadratica che si amplia all'aumentare delle dimensioni del dataset.
• Qualità della Predizione: Nell'esperimento Extra Trees, l'addestramento su 200.000 campioni (10$\times$ il limite della baseline Python) ha ridotto l'RMSE della Put Implied Volatility (IV) dell'8,0% (da 0,361 a 0,333). La separazione di call e put ha ulteriormente ridotto l'RMSE del 27–31%.
• Significatività Statistica: Un test Wilcoxon signed-rank ha confermato che il k-d tree di Mojo è strettamente più veloce del k-d tree di scikit-learn su tutti gli otto dataset ($p < 0,01$), con un'accelerazione media geometrica di 10,8$\times$ (95% CI: [5,94$\times$, 16,62$\times$]).

Significato e Rivendicazioni
Il documento sostiene di essere il primo studio di livello di sistema, aperto e compatibile con Python sull'efficienza dell'inferenza dell'IA finanziaria su scala. Il suo significato primario risiede nel dimostrare che il co-design tra algoritmo, layout di memoria, hardware e linguaggio può produrre un'accelerazione operativamente significativa senza sacrificare l'esattezza o la compatibilità con Python.

Gli autori sostengono che Mojo colmi il divario tra la flessibilità della ricerca in Python e le prestazioni dei sistemi di produzione in C++. Abilitando una singola codebase che raggiunge una velocità vicina a quella del C++ ottimizzato (circa il 60% della velocità C++ ottimizzata in un confronto specifico) offrendo al contempo un'accelerazione di 10$\times$ rispetto alle librerie Python standard, questo lavoro posiziona Mojo come uno stack scalabile e pronto per la produzione per l'IA finanziaria. I risultati suggeriscono che, man mano che i volumi di dati finanziari crescono verso le scale di livello tick, la scalabilità sub-quadratica di questo approccio diventerà sempre più critica per mantenere i vincoli di latenza in tempo reale. Si afferma inoltre che i principi sono applicabili ad altri campi ad alta intensità di dati che richiedono il recupero esatto dei vicini più vicini, come la genomica e la cybersecurity.