ScribeTokens: Fixed-Vocabulary Tokenization of Digital Ink

Le papier présente ScribeTokens, une méthode de tokenisation à vocabulaire fixe pour l'encre numérique qui, en décomposant le mouvement du stylo en pas de pixels unitaires et en utilisant une prédiction de token auto-supervisée, surpasse les représentations vectorielles existantes tant pour la génération que pour la reconnaissance de texte manuscrit.

L'essentiel

🖊️ Le Problème : Comment parler à l'ordinateur de votre écriture ?

Imaginez que vous écrivez sur une tablette numérique. Votre stylo ne laisse pas seulement une image fixe (comme une photo), il laisse une trace vivante : un flux de coordonnées (x, y) qui bouge dans le temps. C'est ce qu'on appelle l'encre numérique.

Le problème, c'est que les ordinateurs ont du mal à "lire" cette trace.

• L'ancienne méthode (les vecteurs) : C'est comme essayer de décrire un dessin en donnant des coordonnées précises pour chaque point, un par un. C'est très long, très lourd à transporter, et l'ordinateur se perd souvent dans les détails, comme un élève qui compte chaque grain de sable d'une plage au lieu de voir la forme de la plage.
• Les anciennes méthodes "tokens" (mots-clés) : D'autres chercheurs ont essayé de découper l'écriture en petits morceaux (des "mots" ou tokens). Mais c'était comme un dictionnaire incomplet : si le stylo faisait un mouvement un peu inhabituel, l'ordinateur disait "Je ne connais pas ce mot !" (problème de hors-vocabulaire). De plus, ces dictionnaires étaient énormes et fragiles.

✨ La Solution : ScribeTokens (Le "Lego" de l'écriture)

L'auteur, Douglass Wang, propose une nouvelle façon de voir les choses avec ScribeTokens.

Imaginez que vous devez expliquer à un ami comment dessiner un "A" sans lui montrer le papier, juste en lui donnant des instructions.

• Au lieu de dire : "Va à la coordonnée 12,4, puis 12,5, puis 12,6...", ScribeTokens dit : "Descends, puis va en diagonale vers la droite, puis remonte."

Voici comment ça marche, étape par étape :

1. La Décomposition Magique (L'algorithme de Bresenham)

L'idée géniale est de décomposer chaque trait de plume en petits pas unitaires, comme des cases sur un jeu de grille.

• Imaginez que votre écriture est un chemin sur un échiquier géant.
• Au lieu de dire "Je vais du coin en bas à gauche au coin en haut à droite", ScribeTokens dit : "Je fais un pas vers le haut, un pas vers la droite, un pas vers le haut, un pas vers la droite..."
• Il utilise une vieille astuce mathématique (l'algorithme de Bresenham) pour tracer ces lignes parfaitement, même si les points ne sont pas collés les uns aux autres.

2. Le Vocabulaire de 10 Mots (Le Kit de Base)

C'est ici que la magie opère. Au lieu d'avoir un dictionnaire de 10 000 mots, ScribeTokens n'a besoin que de 10 symboles de base :

• 8 flèches pour les directions (Haut, Bas, Gauche, Droite, et les 4 diagonales).
• 2 états pour le stylo : "Stylo posé" (on écrit) et "Stylo levé" (on bouge sans écrire).

C'est comme si vous pouviez écrire n'importe quelle phrase, dessiner n'importe quel objet, en n'utilisant que ces 10 symboles. C'est simple, robuste et il n'y a jamais de mot inconnu, car n'importe quel mouvement peut être décomposé en ces pas simples.

3. La Compression (Le Résumeur Intelligent)

Même avec 10 symboles, une phrase entière donnerait une longue liste de flèches. Pour rendre ça rapide, l'ordinateur utilise une technique appelée BPE (Byte-Pair Encoding).

• C'est comme un résumeur automatique : au lieu de dire "Haut, Haut, Haut, Haut", il apprend à dire "Montée-Longue".
• Cela réduit énormément la taille des données, comme compresser un fichier ZIP, mais en gardant toute la structure du dessin.

🚀 Les Résultats : Pourquoi c'est une révolution ?

L'auteur a testé cette méthode sur deux tâches principales : reconnaître ce qu'on a écrit et générer de l'écriture à partir de texte.

1. Pour la Reconnaissance (Lire l'écriture) :

   • Sans entraînement préalable, ScribeTokens bat déjà les anciennes méthodes vectorielles. C'est comme si un élève qui n'a jamais fait de maths pouvait résoudre un problème mieux que ceux qui ont étudié des formules compliquées, simplement parce qu'il a une meilleure méthode de raisonnement.
   • Avec un petit entraînement supplémentaire (pré-entraînement), il devient le champion incontesté, avec très peu d'erreurs.

2. Pour la Génération (Écrire à la place de l'humain) :

   • C'est là que la différence est énorme. Les anciennes méthodes vectorielles échouaient lamentablement (70% d'erreurs !), produisant des gribouillis illisibles.
   • ScribeTokens, lui, produit une écriture claire et lisible. C'est la différence entre un robot qui bégaye et un calligraphe professionnel.

3. L'Accélérateur de Formation (Le "Pré-entraînement") :

   • L'auteur a découvert une astuce : faire deviner à l'IA "quel est le prochain pas de plume ?" avant même de lui apprendre à lire ou écrire.
   • C'est comme apprendre à un enfant à marcher en lui faisant faire des pas sur un tapis avant de lui apprendre à courir.
   • Résultat : L'IA apprend 83 fois plus vite avec cette méthode !

🎯 En Résumé

ScribeTokens est comme un nouveau langage universel pour l'écriture manuscrite.

• Au lieu de parler en coordonnées complexes (mathématiques pures), il parle en directions simples (comme un jeu de l'oie).
• Il est infaillible (pas de mots inconnus).
• Il est rapide (très compressé).
• Il rend l'ordinateur plus intelligent pour lire et écrire, en lui apprenant d'abord à comprendre la géométrie du mouvement.

C'est une preuve que parfois, pour résoudre un problème complexe, il suffit de revenir à l'essentiel : décomposer le mouvement en petits pas simples et logiques.

Résumé technique

1. Problématique

Le digital ink (l'encre numérique), défini comme le flux de coordonnées capturé par un stylet ou un écran tactile, manque de représentation unifiée. Les approches existantes souffrent de limitations majeures :

• Représentations vectorielles (ex: Point-3, Point-5) : Elles encodent l'encre comme une séquence de coordonnées continues. Cela génère des séquences très longues, nécessite des choix de conception complexes (normalisation, gestion des séquences) et souffre d'instabilité lors de l'entraînement pour les tâches de génération (réseaux de densité de mélange).
• Représentations par tokens existantes : Bien qu'elles permettent une compression via le Byte-Pair Encoding (BPE) et un entraînement plus stable, elles présentent des défauts critiques :
  • Problèmes de hors-vocabulaire (OOV) pour les coordonnées non vues.
  • Vocabulaires de base trop grands, dépendant de la résolution du canevas.
  • Syntaxe fragile : certaines séquences générées ne se décodent pas en encre valide.
  • Performance inférieure aux vecteurs sur les tâches de reconnaissance sans pré-entraînement.

2. Méthodologie : ScribeTokens

Les auteurs proposent ScribeTokens, une méthode de tokenisation qui décompose le mouvement du stylo en étapes unitaires de pixels, garantissant une syntaxe robuste et l'absence de tokens hors-vocabulaire.

Principes clés :

1. Décomposition de Bresenham : Au lieu de traiter les points bruts, l'algorithme rasterise les segments de ligne entre deux points consécutifs en utilisant l'algorithme de Bresenham. Cela transforme le mouvement en une séquence de pas unitaires sur une grille discrète.
2. Encodage directionnel (Freeman Chain Codes) : Chaque pas unitaire est encodé comme l'un des 8 tokens directionnels (les 4 cardinaux : →, ↑, ←, ↓ et les 4 diagonaux : ↗, ↖, ↙, ↘).
3. Tokens d'état du stylo : Deux tokens supplémentaires signalent l'état du stylo : [DOWN] (stylo posé) et [UP] (stylo levé).
4. Vocabulaire fixe : Le vocabulaire de base est fixe et ne compte que 10 tokens.
   • Cela élimine le problème OOV par construction (tout mouvement peut être décomposé en ces 10 tokens).
   • Cela rend la représentation invariante au taux d'échantillonnage : deux tracés géométriquement identiques mais avec des densités de points différentes produisent la même séquence de tokens.
5. Compression BPE : Une fois la séquence de base générée, le BPE est appliqué pour compresser les séquences. Les tokens d'état (UP/DOWN) ne sont jamais fusionnés, garantissant que les limites des traits restent explicites.

Détokenisation :

Pour la génération, la séquence de tokens est reconvertie en coordonnées entières via des pas unitaires, puis mise à l'échelle et lissée (filtre de Savitzky-Golay) pour atténuer les artefacts en escalier de la discrétisation.

3. Contributions Principales

1. ScribeTokens : Une tokenisation canonique, sans OOV, avec un vocabulaire de base fixe de 10 tokens et une syntaxe robuste. C'est la seule représentation par token à surpasser les vecteurs sur la reconnaissance sans pré-entraînement.
2. Pré-entraînement par prédiction de token suivant (Next-Ink-Token Prediction) : Les auteurs montrent que cette stratégie d'apprentissage auto-supervisé est hautement efficace pour les tokens. Elle améliore systématiquement la reconnaissance et accélère la convergence jusqu'à 83 fois par rapport à l'entraînement sans pré-entraînement.
3. Analyse comparative : Mise en évidence que les représentations par tokens sont bien supérieures aux vecteurs pour la génération de texte manuscrit, tandis que les vecteurs souffrent d'instabilité et de séquences trop longues.

4. Résultats Expérimentaux

Les expériences ont été menées sur deux jeux de données : IAM (lignes de texte, séquences longues, peu de données) et DeepWriting (mots individuels, plus de données).

Reconnaissance de texte manuscrit (HTR) :

• Sans pré-entraînement : ScribeTokens obtient les meilleurs résultats parmi les tokens (10,75% CER sur DeepWriting), surpassant Point-5. Cependant, sur IAM, Point-5 reste légèrement meilleur (9,43% vs 13,15% pour ScribeTokens).
• Avec pré-entraînement : ScribeTokens + Pré-entraînement atteint les meilleurs résultats globaux sur les deux jeux de données :
  • IAM : 8,27% CER (vs 9,43% pour Point-5).
  • DeepWriting : 9,83% CER.
• Accélération : Le pré-entraînement réduit le nombre d'époques nécessaires pour converger de 21x sur IAM pour la reconnaissance et de 83x pour la génération.

Génération de texte manuscrit (HTG) :

• Les tokens surpassent massivement les vecteurs.
• Sans pré-entraînement : ScribeTokens obtient 17,33% CER sur IAM contre 70,29% pour les vecteurs (Point-5).
• Avec pré-entraînement : ScribeTokens + Pré-entraînement atteint 10,45% CER sur IAM, le meilleur résultat de toutes les méthodes.

Analyse des mécanismes :

• Attention : L'analyse de l'attention montre que les modèles pré-entraînés avec ScribeTokens allouent 91,2% de leur attention aux tokens d'encre (contre 66,9% sans pré-entraînement), indiquant qu'ils apprennent à décoder le signal graphique plutôt que de mémoriser des motifs de texte.
• Échec des autres tokens : Les modèles comme TextTokens (qui sérialisent les coordonnées en chaînes de caractères) échouent souvent car leur vocabulaire lexical n'a pas de sens géométrique, empêchant l'extraction efficace du signal d'encre.

5. Signification et Conclusion

Ce travail démontre que la tokenisation de l'encre numérique via une décomposition géométrique discrète (ScribeTokens) est une approche supérieure aux représentations continues pour les modèles de type Transformer.

• Stabilité et Efficacité : La méthode élimine les problèmes de vocabulaire infini et de syntaxe fragile, permettant une compression agressive tout en restant invariante à l'échantillonnage.
• Synergie Pré-entraînement/Tokenisation : L'article établit un lien crucial entre le type de représentation et l'efficacité du pré-entraînement. Le pré-entraînement "Next-Token" est crucial pour les tokens (qui souffrent d'un problème de démarrage à froid sans information spatiale) mais peut même nuire aux représentations vectorielles continues qui possèdent déjà un biais inductif spatial.
• Impact : ScribeTokens permet d'atteindre des performances de pointe en reconnaissance et en génération, en particulier dans des régimes à faible quantité de données, en combinant une tokenisation robuste et un pré-entraînement auto-supervisé efficace.

En résumé, ScribeTokens fournit un "vocabulaire" universel pour l'encre numérique, ouvrant la voie à l'application des techniques de modélisation du langage (LLM) les plus avancées à la reconnaissance et à la génération de l'écriture manuscrite.