🤖 machine learning

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

Cet article démontre qu'une implémentation d'un arbre k-d SIMD exact basée sur Mojo surpasse de manière significative les méthodes existantes de scikit-learn en termes de vitesse et de scalabilité pour les séries temporelles financières à haute fréquence, permettant un apprentissage des plus proches voisins en temps réel et l'amélioration des modèles de tarification de dérivés sans sacrifier la précision.

Auteurs originaux : Henry Han, Diane Li

Publié 2026-06-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Henry Han, Diane Li

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le gros problème : Le dilemme de "l'aiguille dans une botte de foin"

Imaginez que vous êtes un trader financier. Chaque seconde, vous devez prendre une décision basée sur le marché actuel. Pour ce faire, vous consultez votre « banque de mémoire » — un historique massif de la façon dont le marché s'est comporté par le passé. Vous voulez trouver les moments exacts de l'histoire qui ressemblent le plus à aujourd'hui pour prédire ce qui va se passer ensuite.

Le problème est que cette « banque de mémoire » devient énorme (des millions de points de données).

L'ancienne méthode (Python/Scikit-learn) : Imaginez essayer de trouver un livre spécifique dans une bibliothèque en parcourant chaque allée, en vérifiant chaque livre, un par un. C'est précis, mais c'est incroyablement lent. À mesure que la bibliothèque s'agrandit, vous devenez de plus en plus lent.
La méthode « rapide » (C++) : Imaginez engager une équipe de coureurs super rapides pour effectuer la même recherche. Ils sont rapides, mais ils parlent une langue différente de celle de vos chercheurs. Vous devez traduire vos idées dans leur langue, ce qui est lent, coûteux et sujet aux erreurs.

La solution : Mojo

Les auteurs présentent Mojo, un nouveau langage de programmation qui est comme un « Python super-vitaminé ». Il parle la même langue que les chercheurs (facile à écrire) mais fonctionne avec la vitesse des coureurs super rapides.

Ils ont utilisé Mojo pour construire une manière plus intelligente de rechercher cet historique financier. Au lieu de vérifier chaque livre (point de donnée), ils ont construit un système de classement intelligent (un « arbre k-d » ou k-d tree) qui les aide à sauter de larges sections de la bibliothèque qui ne contiennent certainement pas la réponse.

Comment ils l'ont rendu rapide (Les trois astuces)

Le document explique qu'ils n'ont pas seulement utilisé un système de classement intelligent ; ils l'ont optimisé de trois manières spécifiques pour le rendre fulgurant :

La « division intelligente » (Splitting basé sur la variance) :
- Analogie : Imaginez trier un tas de vêtements en désordre. Au lieu de simplement les diviser en « chemises contre pantalons », vous regardez le tas et demandez : « Quelle caractéristique sépare le plus ces articles ? » Peut-être divisez-vous d'abord par « couleur » parce que cela crée les groupes les plus nets.
- Dans le document : L'algorithme examine les données financières et trouve la caractéristique spécifique (comme la volatilité ou le momentum des prix) qui varie le plus. Il divise les données à cet endroit en premier, créant des groupes plus serrés et plus faciles à rechercher.
Le « sol plat » (Stockage contigu en buffers plats) :
- Analogie : Imaginez que vos livres sont stockés dans une bibliothèque où certains sont dans une boîte, d'autres sur une étagère et d'autres dans un sous-sol, et que vous devez faire des allers-retours pour les récupérer. C'est lent. Maintenant, imaginez que tous les livres sont alignés parfaitement en une seule longue rangée sur une seule étagère. Vous pouvez les saisir d'un seul mouvement fluide.
- Dans le document : Ils ont stocké les données dans un seul bloc de mémoire continu. Cela permet au « préchargeur » de l'ordinateur (une partie du cerveau qui devine ce dont vous aurez besoin ensuite) de récupérer les données efficacement sans perdre de temps à sauter d'un endroit à l'autre.
Le « super-lecteur » (Vectorisation SIMD) :
- Analogie : Imaginez que vous lisez une liste de nombres. Une personne normale lit un nombre à la fois. Un « Super-Lecteur » (SIMD) peut lire huit nombres à la fois et faire le calcul sur tous ces nombres en un seul clin d'œil.
- Dans le document : Ils ont programmé l'ordinateur pour comparer huit points de données financières simultanément. Cela rend le calcul mathématique de la comparaison entre « aujourd'hui » et « hier » incroyablement rapide.

Les résultats : Vitesse vs Précision

L'équipe a testé cela sur des données financières réelles (actions, ETF et devises) sur deux types de puces informatiques (Intel x86 et Apple M3).

La vitesse :
- Sur les ordinateurs standards (x86), leur nouvelle méthode était 17 à 21 fois plus rapide que l'outil Python standard (scikit-learn).
- Sur les ordinateurs Apple (ARM64), elle était 28 à 43 fois plus rapide que l'outil standard.
- Point crucial : Ils n'ont pas simplement deviné la réponse. Ils ont trouvé la même réponse exacte que la méthode lente, mais beaucoup plus rapidement.
Le « Pourquoi » (La surprise ARM64) :
- Sur les puces Apple, la méthode standard de « force brute » (vérifier tout) était étonnamment lente car le « Super-Lecteur » (SIMD) de la puce était plus étroit que ce que le code attendait. Cependant, comme le « Système de classement intelligent » (arbre k-d) des auteurs sautait tellement de vérifications inutiles, cela n'avait pas d'importance. C'était toujours la méthode la plus rapide, avec une marge énorme.

Le gain dans le monde réel : De meilleures prédictions

Le document ne s'est pas arrêté à la vitesse. Ils ont montré que la rapidité permet de faire plus de travail.

Ils ont entraîné un modèle pour prédire la « volatilité implicite » (une mesure du risque pour les options sur actions).
Grâce à la rapidité de leur système, ils ont pu entraîner le modèle sur 10 fois plus de données que ce que le système Python standard pouvait gérer dans le même laps de temps.
Le résultat : En utilisant plus de données, le modèle est devenu 8 % plus précis. Cela prouve que la vitesse n'est pas seulement une question d'attendre moins longtemps ; c'est une question d'apprendre mieux.

Résumé

Le document soutient que pour gérer les quantités massives de données dans la finance moderne, nous ne pouvons pas nous contenter d'outils lents et faciles (Python) ou d'outils difficiles et rapides (C++). Nous avons besoin d'un juste milieu.

Mojo offre ce juste milieu. En combinant un algorithme de recherche intelligent, une manière ordonnée de stocker les données et un moteur de calcul de type « super-lecture », ils ont créé un système qui est :

Exact : Il ne devine pas ; il trouve la vraie réponse.
Rapide : Il est 17 à 43 fois plus rapide que les outils standards actuels.
Évolutif : Il devient encore plus puissant à mesure que la quantité de données augmente, permettant aux modèles financiers d'apprendre à partir d'histoques beaucoup plus vastes et de faire de meilleures prédictions.

Résumé Technique : Apprentissage de Voisin Proche Exact et Rapide pour les Séries Temporelles Financières à Haute Fréquence

Énoncé du Problème
L'IA financière entre dans une ère de mise à l'échelle où les modèles doivent ingérer des corpus historiques massifs (actions, ETF, FX, options) pour soutenir le trading en temps réel, la gestion des risques et la tarification des dérivés. Un goulot d'étranglement critique existe dans la pile actuelle : bien que les outils basés sur Python (NumPy, scikit-learn) offrent de la flexibilité, ils souffrent d'un surcoût d'interprétation, d'une saturation de la bande passante mémoire et d'une mauvaise localité de cache lors de l'interrogation de centaines de milliers d'états historiques. À l'inverse, les solutions C++ et FPGA offrent de la vitesse mais créent un écart « de la recherche à la production » en raison de la nécessité de bases de code distinctes et d'une optimisation manuelle. Le défi spécifique abordé est l'inférence de voisin le plus proche (KNN) exact pour les séries temporelles à haute fréquence, où le coût linéaire de la recherche par force brute ( $O(n \cdot d)$ ) devient prohibitif pour les budgets de latence en temps réel, alors que les méthodes approximatives (comme HNSW) sacrifient l'exactitude requise pour certaines applications financières.

Méthodologie
Les auteurs proposent un arbre k-d SIMD en Mojo conçu spécifiquement pour les corpus de séries temporelles financières. Mojo, un langage système compilé avec une syntaxe compatible avec Python, permet le co-design de l'algorithme, de la disposition de la mémoire et du matériel sans quitter l'écosystème Python. La méthodologie intègre trois optimisations fondamentales :

Division Basée sur la Variance : Contrairement aux divisions classiques basées sur la médiane, l'arbre sélectionne l'axe de division selon la dimension présentant la variance maximale ( $j^* = \arg\max \text{Var}(\{x_{i,j}\})$ ). Cela concentre l'élagage précoce sur les caractatures financières les plus discriminantes (rendements, volatilité, momentum), créant des sous-régions plus serrées.
Stockage en Tampon Plat Contigu : Les vecteurs d'entraînement sont stockés dans un tampon plat en mode ligne majoritaire ( $X \in \mathbb{R}^{n \times d}$ ) indexé par un tableau permuté. Les nœuds feuilles sont définis par des décalages entiers, permettant aux candidats d'être lus comme des blocs de mémoire contigus. Cela élimine le surcoût lié à la poursuite de pointeurs (pointer-chasing) et garantit l'alignement des lignes de cache.
Noyaux Vectorisés à la Compilation : Les calculs de distance utilisent la vectorisation SIMD (Single Instruction, Multiple Data). Le noyau est spécialisé à la compilation (comptime) pour des dimensions spécifiques (ex: $d=16$ ou $d=24$ ) et des largeurs SIMD, générant un code entièrement déroulé et sans scalaire. La distance euclidienne au carré est décomposée en blocs parallèles de largeur de registre.

Le système a été évalué sur huit jeux de données financiers (actions américaines, ETF, FX) sur deux architectures matérielles : x86 (Intel/AMD) et ARM64 (Apple M3). Des comparaisons ont été effectuées avec les implémentations par force brute et par arbre k-d de scikit-learn, ainsi qu'avec l'approche de force brute SIMD de Mojo.

Contributions Clés

Implémentation de l'Arbre k-d SIMD en Mojo : Une nouvelle implémentation combinant l'élagage basé sur la variance, la disposition de la mémoire en tampon plat et les noyaux de distance vectorisés à la compilation pour le KNN exact sur de grands jeux de données financiers.
Analyse du Temps d'Exécution Théorique : Une preuve démontrant que, sous des hypothèses d'élagage standard, l'arbre k-d de Mojo domine asymptotiquement la force brute SIMD de Mojo et l'arbre k-d de scikit-learn dans le régime à stock fixe, grand $n$ et dimension modérée.
Co-Design Finance-Matériel : Une approche normalisée d'ingénierie des caractéristiques où les caractéristiques dérivées de l'OHLCV sont alignées avec les largeurs SIMD (16 et 24 valeurs float32 correspondant respectivement à 2 et 3 largeurs de registres), préservant l'interprétabilité financière tout en maximisant le débit.
Validation Empirique : Des benchmarks complets montrant des accélérations significatives sur diverses classes d'actifs et plateformes matérielles, avec une signification statistique confirmée par des tests de rang signé de Wilcoxon.
Démonstration de Scalabilité : Une expérience secondaire utilisant les Extra Trees pour la tarification de la volatilité implicite montre que les gains de débit permettent l'entraînement sur 10 $\times$ plus de données, améliorant directement la précision de la prédiction.

Résultats

Accélération sur x86 ( $d=16$ ) : L'arbre k-d de Mojo a obtenu une accélération de 17,5 à 21,6 $\times$ par rapport à l'arbre k-d de scikit-learn et de 1,2 à 1,3 $\times$ par rapport à la force brute de scikit-learn sur des jeux de données allant de 143k à 277k échantillons.
Accélération sur ARM64 ( $d=24$ ) : La méthode a obtenu une accélération de 28,1 à 43,5 $\times$ par rapport à la force brute de scikit-learn sur Apple M3. Notamment, sur ARM64, le noyau de force brute SIMD de Mojo était 780 à 1549 $\times$ plus lent que l'arbre k-d en raison d'un décalage entre la largeur SIMD à la compilation (optimisée pour les registres 256 bits de x86) et les registres natifs 128 bits d'ARM. Cependant, l'élagage algorithmique de l'arbre k-d ( $O(n^{1-1/d})$ ) l'a rendu immunisé contre cette pénalité spécifique au matériel, maintenant des gains massifs.
Exposants de Mise à l'Échelle : L'ajustement empirique de la complexité temporelle $T(n) = Cn^\alpha$ a produit un exposant de 1,755 pour l'arbre k-d de Mojo (requête uniquement), contre 1,885 pour la force brute et 2,320 pour l'arbre k-d de scikit-learn. Cela confirme une mise à l'échelle sous-quadratique qui s'accentue à mesure que la taille du jeu de données augmente.
Qualité de Prédiction : Dans l'expérience Extra Trees, l'entraînement sur 200 000 échantillons (10 $\times$ la limite de base de Python) a réduit l'RMSE de la volatilité implicite (IV) du Put de 8,0 % (de 0,361 à 0,333). La séparation des calls et des puts a encore réduit l'RMSE de 27 à 31 %.
Signification Statistique : Un test de rang signé de Wilcoxon a confirmé que l'arbre k-d de Mojo est strictement plus rapide que l'arbre k-d de scikit-learn sur les huit jeux de données ( $p < 0,01$ ), avec une accélération de la moyenne géométrique de 10,8 $\times$ (IC 95 % : [5,94 $\times$ , 16,62 $\times$ ]).

Signification et Revendications
L'article affirme être la première étude de niveau système, compatible avec Python et en open-source, de l'efficacité de l'inférence de l'IA financière à grande échelle. Sa principale importance réside dans la démonstration que le co-design entre l'algorithme, la disposition de la mémoire, le matériel et le langage peut produire une accélération opérationnellement significative sans sacrifier l'exactitude ou la compatibilité avec Python.

Les auteurs soutiennent que Mojo comble le fossé entre la flexibilité de la recherche en Python et la performance des systèmes de production en C++. En permettant un code unique qui atteint une vitesse proche de celle du C++ optimisé (environ 60 % de la vitesse du C++ optimisé dans une comparaison spécifique) tout en offrant une accélération de 10 $\times$ par rapport aux bibliothèques Python standards, ce travail positionne Mojo comme une pile évolutive et prête pour la production. Les résultats suggèrent qu'à mesure que les volumes de données financières tendront vers des échelles de type tick-level, la mise à l'échelle sous-quadratique de cette approche deviendra de plus en plus critique pour maintenir les contraintes de latence en temps réel. Les principes sont également revendiqués comme applicables à d'autres domaines intensifs en données nécessitant la recherche de voisins les plus proches exacts, tels que la génomique et la cybersécurité.