Mathématiques

Un coude, sinon rien

elbow-helper détecte les coudes des courbes de rendements décroissants, avec une incertitude chiffrée. Quand la preuve manque, il s'abstient.

Le logo d'elbow-helper : une armure articulée de coude, dessinée comme une gravure ancienne.

Combien de groupes retenir dans une classification automatique ? Quand arrêter d'entraîner un modèle ? À partir de quel budget un canal publicitaire sature-t-il ? Ces trois questions partagent une même silhouette : une courbe de rendements décroissants, qui monte vite puis s'aplatit. Le point où elle cesse de payer porte un nom d'anatomie : le coude. Avant lui, chaque unité investie rapporte ; après lui, on s'obstine.

Trouver ce point semble facile, et c'est bien le piège : un algorithme de détection de coude répond toujours quelque chose, même sur une droite parfaite ou sur du bruit pur. elbow-helper pose une question plus dure : ce candidat est-il fort, unique, persistant, reproductible, improbable sous un modèle sans coude ? Si une seule de ces conditions échoue, il s'abstient et dit pourquoi.

La courbe d'inertie d'un k-means en fonction du nombre de groupes : elle descend vite puis s'aplatit, le coude détecté est marqué avec son intervalle de confiance.

Le cas d'école : l'inertie d'un k-means selon le nombre de groupes. Le coude détecté, son intervalle de confiance et les preuves chiffrées à côté.


Motivation

Les heuristiques existantes, à commencer par l'algorithme Kneedle qui fait référence, excellent à proposer un emplacement. Elles ne portent en revanche aucune notion de confiance : un point, sans marge d'erreur, sans probabilité, sans droit de retrait. Sur une courbe bruitée, ce point isolé est facile à surinterpréter : on choisit quatre groupes, on dimensionne un cache, on arrête une expérience, sur la foi d'un artefact du bruit.

Un radiologue devant un cliché flou ne diagnostique pas ; il écrit que l'examen ne permet pas de conclure et prescrit un second cliché. Une procédure statistique devant une courbe bruitée mérite la même retenue : conclure seulement ce que la donnée supporte. Le parallèle a sa limite, et elle éclaire le projet : le radiologue engage un jugement, la procédure applique des seuils calibrés une fois pour toutes, ce qui la rend plus prévisible et moins fine à la fois.

La priorité de conception d'elbow-helper est donc explicite : minimiser les faux coudes, quitte à s'abstenir plus souvent. Le contrat de sortie l'impose au code appelant : soit un ClearKnee avec position, intervalle de confiance à 90 % et preuves chiffrées, soit un NoClearKnee avec un code de raison lisible en machine. Aucun repli silencieux vers une estimation douteuse : l'abstention se gère, elle ne se contourne pas.


Comment ça marche

Tout commence par une définition honnête du mot « coude ». Prenez une courbe en \(\sqrt{x}\), qui monte vite puis se calme, et soustrayez-lui la diagonale qui relie ses deux extrémités : il reste une bosse, nulle aux deux bouts, maximale là où la courbe s'écarte le plus d'une droite. Ce sommet est le coude. Après normalisation des données dans le carré unité, la courbe de différence s'écrit :

$$d(x_i) \;=\; y_{\text{norm}}(x_i) - x_{\text{norm},\,i}$$

Ses maxima locaux sont les candidats. Un seuil de sensibilité décide ensuite si un sommet est un vrai coude ou une simple ondulation : le candidat doit dominer son voisinage d'une marge proportionnelle à un paramètre \(S\) :

$$T \;=\; d_{\max} - S \cdot \overline{|\Delta x_{\text{norm}}|}$$

où la barre désigne l'espacement moyen entre abscisses consécutives. Plus \(S\) est grand, plus la marge exigée est large. Cette recherche est rejouée sur toute une grille de lissages et de sensibilités, et seuls survivent les candidats qui reviennent au même endroit à travers les échelles : un coude réel persiste quand on floute un peu la courbe, un accident de bruit disparaît.

Vient ensuite la confirmation par modèle. Un vrai coude est un changement de pente : une ligne droite, puis une autre pente après le point \(k\). La fonction charnière \(\max(0, x - k)\), exactement nulle avant \(k\) et linéaire après, fabrique cette ligne brisée d'un seul tenant, sans saut :

$$y \;=\; a + b\,x + c \cdot \max(0,\; x - k)$$

Le coefficient \(c\) porte toute l'histoire du coude : \(c = 0\) redonne une droite sans coude, et plus \(c\) s'éloigne de zéro, plus la pente casse fort en \(k\). Ce modèle brisé doit battre la droite simple sur deux tableaux. D'abord en validation croisée par blocs : on retire des tronçons contigus entiers de la courbe et l'on vérifie que le modèle prédit bien les tronçons cachés, un point isolé étant trop facile à deviner d'après ses voisins immédiats. Ensuite au sens du BIC (Bayesian Information Criterion), un score qui récompense la qualité d'ajustement tout en faisant payer chaque paramètre supplémentaire : le coude doit gagner sa place.

Restent deux épreuves de robustesse. Le bootstrap : on rejoue la recherche entière sur des copies de la courbe obtenues en rebrassant le bruit résiduel, et le coude doit être redétecté dans au moins 90 % des rejeux, au même endroit, avec un intervalle serré. Le test du modèle nul, enfin : on simule des milliers de droites pures portant le même niveau de bruit et l'on mesure la probabilité \(p\) qu'une droite sans aucun coude produise, par hasard, une preuve aussi forte que celle observée. Il faut :

$$\widehat{p}_{\text{détection}} \;\ge\; 0{,}9 \qquad\text{et}\qquad p_{\text{nul}} \;\le\; 0{,}01$$

Seul un candidat qui franchit toutes les portes devient un ClearKnee. La figure de diagnostic résume ce dossier de preuves à côté de la courbe ; en cas d'abstention, elle bascule vers un état honnête, courbe grisée et raison affichée, jamais un marqueur qui suggérerait plus de certitude que les données n'en contiennent.

Le même coude discret à deux niveaux de bruit : à faible bruit le coude est détecté avec son intervalle, à fort bruit la figure grisée annonce une abstention.

Le même coude discret, à deux niveaux de bruit : détecté et encadré à gauche, abstention assumée à droite.

Et quand la courbe change plusieurs fois de régime, trois paliers de prix sur une courbe de demande par exemple, la question devient : combien de cassures, et où ? robust_knees y répond en explorant tous les nombres de segments par programmation dynamique, en départageant les candidats avec un BIC modifié où chaque cassure supplémentaire doit mériter son coût, puis en confirmant le vainqueur par un test de permutation : des milliers de rebrassages de la courbe, aucun ne portant de vraie cassure, doivent presque tous faire moins bien que l'ajustement réel. Comme multiplier les tests multiplie les occasions d'avoir de la chance, une correction de Bonferroni resserre la barre de chaque test en proportion de leur nombre.

Le tout tient avec une seule dépendance de calcul, NumPy : l'algorithme de localisation est réécrit de zéro, et la figure de diagnostic est du SVG écrit à la main, sans bibliothèque graphique. Chaque formule de cette chaîne, de la normalisation au test de permutation, est dérivée pas à pas dans la note mathématique du dépôt (doc/ELBOW-en.tex), écrite intuition d'abord, avec un exemple travaillé avant chaque formule.


Conclusion

Un détecteur qui s'abstient rend un meilleur service qu'un détecteur qui répond toujours. « Pas de coude net » est une vraie information : elle évite de dimensionner un système, d'arrêter une expérience ou de trancher un budget sur un pli du hasard. La confiance affichée se paie en abstentions ; c'est un échange que je revendique.

elbow-helper s'installe en une ligne, pip install elbow-helper, et s'essaie sans rien installer dans le bac à sable en ligne, où la chaîne complète tourne dans votre navigateur sans téléverser vos données. Le code, les exemples et la note mathématique sont sur github.com/warith-harchaoui/elbow-helper. Apportez une courbe ; vous repartirez avec un coude défendable, ou avec une bonne raison de ne pas y croire.

← Retour au blog